2178번 파이썬

dfs가 익숙해서 첨부터 dfs로 풀었는데 vscode상에선 문제없이 잘돌아갔지만 dfs로 풀면 시간 초과가 돼서 계속 답이 틀림...

인터넷 찾아보니 최솟값을 구하는 문제는 bfs로 풀면 훨씬 쉽게 풀린다고 한다. 실제로 저번에 이용했던 deque를 이용해서 구현했더니 코드도 간단해지고 반복문을 여러번 반복하지 않고 최솟값을 금방 구하는것 같다!

 

import sys
input = sys.stdin.readline
from collections import deque
n,m= map(int,input().split())
mat=[list(input()) for _ in range(n)]
'''
def dfs1(mat, cnt, row, col,visited):
    if row == n-1 and col == m-1:
        res.append(cnt)
        return
    for row1 in range(n):
        for col1 in range(m):
            if [row1,col1] not in visited:
                if abs(row1-row)+abs(col1-col)==1 and int(mat[row1][col1])==1:
                    visited.append([row1,col1])
                    mat[row1][col1]=0
                    dfs1(mat,cnt+1,row1,col1,visited)
                    mat[row1][col1]=1
                    visited.remove([row1,col1])
                    return

def dfs(mat,cnt,row,col,visited):
    if row == n-1 and col == m-1:
        print(visited,cnt)
        res.append(cnt)
        return
    #row+1
    if row+1 <= n-1:
        if [row+1,col] not in visited:
            if mat[row+1][col]=='1':#1은 true
                visited.append([row+1,col])
                mat[row+1][col]='0'
                dfs(mat,cnt+1,row+1,col,visited)
                mat[row+1][col]='1'
                visited.remove([row+1,col])
    #row-1
    if row-1 >= 0:
        if [row-1,col] not in visited:
            if mat[row-1][col]=='1':#1은 true
                visited.append([row-1,col])
                mat[row-1][col]='0'
                dfs(mat,cnt+1,row-1,col,visited)
                mat[row-1][col]='1'
                visited.remove([row-1,col])
    #col+1
    if col+1 <= m-1:
        if [row,col+1] not in visited:
            if mat[row][col+1]=='1':#1은 true
                visited.append([row,col+1])
                mat[row][col+1]='0'
                dfs(mat,cnt+1,row,col+1,visited)
                mat[row][col+1]='1'
                visited.remove([row,col+1])
    #col-1
    if col-1 <= m-1:
        if [row,col-1] not in visited:
            if mat[row][col-1]=='1':#1은 true
                visited.append([row,col-1])
                mat[row][col-1]='0'
                dfs(mat,cnt+1,row,col-1,visited)
                mat[row][col-1]='1'
                visited.remove([row,col-1])
    return
'''
def bfs(mat):
    q=deque([[0,0]])
    r=[1,-1,0,0]
    c=[0,0,1,-1]
    while q:
        item = q.popleft()
        a,b=item[0],item[1]
        for i in range(4):
            A=a+r[i]
            B=b+c[i]
            if 0<=A<n and 0<=B<m and mat[A][B]=='1':
                q.append([A,B])
                mat[A][B]=mat[a][b]+1
    print(mat[n-1][m-1])

mat[0][0]=1
bfs(mat)