[백준] 2178번: 미로탐색 (sol.X)

풀이시간: X

1. 나의 풀이

from collections import deque

N, M = map(int, input().split())

adj = []

for _ in range(N):
    row_list = []
    row = input()
    for i in range(M):
        row_list.append(int(row[i]))
    adj.append(row_list)

chk = [[False] * M for _ in range(N)]

dy = (0, 1, 0, -1)
dx = (1, 0, -1, 0)

def is_valid_coord(y, x):
	return 0 <= y < N and 0 <= x < M



def bfs(start_y, start_x):
    q = deque()
    q.append((start_y, start_x))
    chk[start_y][start_x] = True

    ans = 1

    while len(q) > 0:
        y, x = q.popleft()

        if chk[N-1][M-1] == True:
             return ans

        ans += 1

        for k in range(4):
            ny = y + dy[k]
            nx = x + dx[k]
            if is_valid_coord(ny, nx) and not chk[ny][nx] and adj[ny][nx] == 1:
                chk[y][x] = True
                q.append((ny, nx))
    

print(bfs(0, 0))

• 최소의 칸수를 구하는 것이므로 BFS 사용
• 미로를 좌표로 옮긴다.
• 큐에 넣고 빼고를 반복을 하며 한 작업이 끝나면 이동한 칸 수 +1 칸을 한다.
• 마지막 칸이 True가 되면 모든 작업을 끝내고 ans 값을 출력한다.
• 자꾸 None값이 반환된다.. while문 중간에 끝나는 듯....

2. 또다른 풀이

from collections import deque

dy = (0, 1, 0, -1)
dx = (1, 0, -1, 0)
N, M = map(int, input().split())
board = [input() for _ in range(N)]

def is_valid_coord(y, x):
	return 0 <= y < N and 0 <= x < M

def bfs():
    chk = [[False] * M for _ in range(N)]
    chk[0][0] = True
    dq = deque()
    dq.append((0, 0, 1)) # 몇 칸 지났는 지 표기 
    while dq:
        y, x, d = dq.popleft()

        if y == N - 1 and x == M - 1:
             return d
        
        nd = d + 1

        for k in range(4):
            ny = y + dy[k]
            nx = x + dx[k]
            if is_valid_coord(ny, nx) and board[ny][nx] == '1' and not chk[ny][nx]:
                chk[ny][nx] = True
                dq.append((ny, nx, nd))

print(bfs())

3. 보완할 것

• 노드에 좌표 정보뿐만 아니라 추가 정보를 넣을 수 있다.
• 한작업에서 노드끼리 공유하는 정보는 노드에 넣는다.
• 카운트시 작업이 시작될 때 카운트를 할 수 있도록 하자.