백준 2178 미로 탐색(BFS & DFS 기초)

문제는 2차원 배열에 관한 탐색 기초문제이다.
즉, 주어진 이동조건에 따라 mx, my를 만들어야 한다는 점이다.

DFS 이용 (시간 초과)

mx = [1, -1, 0, 0]
my = [0, 0, -1, 1]

def dfs(x,y, cnt):
    if x == n-1 and y == m-1:
        global min_cnt      #min 값 비교를 위한 변수
        min_cnt = min(min_cnt, cnt)

        return

    visit[x][y] = 1     # 방문처리

    for i in range(4):
        dx = x + mx[i]
        dy = y + my[i]

        if 0 <= dx < n and 0 <= dy < m:
            if lis[dx][dy] == 1 and visit[dx][dy] == 0:
                dfs(dx, dy, cnt+1)

    visit[x][y] = 0     # 다음 재귀를 위해 방문 처리를 다시 풀어줘야함.

n, m = map(int, input().split())
lis = []
visit = [[0] * m for _ in range(n)]

for _ in range(n):
    lis.append(list(map(int, input())))

min_cnt = n*m
dfs(0, 0, 1)
print(min_cnt)

BFS 이용 (통과)

from collections import deque

mx = [1, -1, 0, 0]
my = [0, 0, -1, 1]

def bfs(x, y):
    que = deque()
    que.append((x,y))
    visit[x][y] = 1     # 방문처리

    while que:
        tx, ty = que.popleft()

        for i in range(4):
            dx = tx + mx[i]
            dy = ty + my[i]

            if 0 <= dx < n and 0 <= dy < m and lis[dx][dy] == 1 and not visit[dx][dy]:
                visit[dx][dy] = visit[tx][ty] + 1
                que.append((dx, dy))

    return visit[n-1][m-1]


n, m = map(int, input().split())
lis = []
visit = [[0] * m for _ in range(n)]

for _ in range(n):
    lis.append(list(map(int, input())))

print(bfs(0,0))

visit에 해당 x,y일 때의 좌표에 대한 최소 움직임 값을 visit 함수에 담는다. 결론적으로 visit 배열의 끝 값이 정답이다.