백준 2178 미로탐색 Python

Derhon·2023년 11월 18일
0
post-thumbnail

백준 2178 미로탐색

1트

from collections import deque
import sys

N, M = list(map(int, sys.stdin.readline().rstrip().split()))
graph = [[False] * M for _ in range(N)]
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]

for i in range(N): #그래프 만들기
    line = list(map(int, list(sys.stdin.readline().rstrip())))
    for j in range(M):
        if line[j] == 1:
            graph[i][j] = True

def bfs(x, y):
    q = deque([(x, y)])
    while q:
        prev_x, prev_y = q.popleft()
        for i in range(4):
            next_x = prev_x + dx[i]
            next_y = prev_y + dy[i]
            if 0 <= next_x < N and 0 <= next_y < M:
                if graph[next_x][next_y] == 1:
                    q.append((next_x, next_y))
                    graph[next_x][next_y] = graph[prev_x][prev_y] + 1

bfs(0, 0)
print(graph[N-1][M-1])

처음에 count 값을 선언하고 그걸로 값을 계산하다가 한계를 느껴 graph 자체의 값을 변경하는 것으로 바꿨다.
참고

2트

from collections import deque
import sys

N, M = list(map(int, sys.stdin.readline().rstrip().split()))
graph = [list(map(int, ' '.join(sys.stdin.readline().rstrip().split()))) for _ in range(N)]
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]

def bfs():
    q = deque([(0, 0)])
    while q:
        prev_x, prev_y = q.popleft()
        for i in range(4):
            next_x, next_y = prev_x + dx[i], prev_y + dy[i]
            if 0 <= next_x < N and 0 <= next_y < M:
                if graph[next_x][next_y] == 1:
                    q.append((next_x, next_y))
                    graph[next_x][next_y] = graph[prev_x][prev_y] + 1

bfs()
print(graph[N-1][M-1])

위 블로그 글을 공부한 다음 안보고 풀어봤다.
2번 푸니까 예전에 공부했떤 BFS가 떠오른다

profile
🧑‍🚀 이사했어요 ⮕ https://99uulog.tistory.com/

0개의 댓글