[백준 2178] 미로 탐색 (Python)

👩🏻‍💻문제링크

[백준 2178] 미로 탐색 (Python)

✍️Idea Sketch

2021-07-28

1. 백준 입력값 처리에서 헤맸던 문제

• sys.stdin.readline() : 한 줄을 입력받으며, input()과 비슷하다.
• split() : 띄어쓰기를 기준으로 원소를 나눈다.
• rstrip() : 우측 \n를 제거한다.
• list(map(int, sys.stdin.readline().rstrip())) : 한 줄 입력받고, 우측 \n을 제거한 후, 모든 원소를 int형으로 변환한 배열을 생성한다.

N, M = map(int, sys.stdin.readline().split())
graph = [list(map(int, sys.stdin.readline().rstrip())) for _ in range(N)]

2. dx와 dy를 정의하고, graph 경계값 처리

3. visited 생략가능

✍️소스코드

2021-07-28

112ms 통과, visited 사용

import sys
from collections import deque

N, M = map(int, sys.stdin.readline().split())
graph = [list(map(int, sys.stdin.readline().rstrip())) for _ in range(N)]
visited = [[0 for _ in range(M)] for _ in range(N)]

def bfs(x, y):
  dx = [-1, 1, 0, 0]
  dy = [0, 0, -1, 1]
  queue = deque([(x, y)])
  visited[x][y] = 1
  while queue:
    x, y = queue.popleft()
    for i in range(4):
      nx = x + dx[i]
      ny = y + dy[i]
      if (-1<nx<N) and (-1<ny<M): #1 경계값  [#1부터 #3까지 한 줄로 작성할 경우 124ms]
        if graph[nx][ny]: #2 벽인지 아닌지
            if not visited[nx][ny]: #3 방문여부 
              queue.append((nx, ny))
              visited[nx][ny] = visited[x][y] + 1

  return visited[N-1][M-1]

print(bfs(0, 0))

124ms 통과, visited 생략

• graph[nx][ny]가 0이면 벽
• graph[nx][ny]가 1이면 처음 방문한 노드
• graph[nx][ny]가 1보다 크면 방문한 적 있는 노드

import sys
from collections import deque

N, M = map(int, sys.stdin.readline().split())
graph = [list(map(int, sys.stdin.readline().rstrip())) for _ in range(N)]

def bfs(x, y):
  dx = [-1, 1, 0, 0]
  dy = [0, 0, -1, 1]
  queue = deque([(x, y)])
  while queue:
    x, y = queue.popleft()
    for i in range(4):
      nx = x + dx[i]
      ny = y + dy[i]
      if (-1<nx<N) and (-1<ny<M):
        if graph[nx][ny] == 1:
            queue.append((nx, ny))
            graph[nx][ny] = graph[x][y] + 1

  return graph[N-1][M-1]

print(bfs(0, 0))