[백준] 2178번 - 미로 탐색

참고: https://www.acmicpc.net/problem/2178

 

✔️ 문제

 

 

문제는 다음과 같다.

 

 

✔️ 풀이

 

 

문제에서 유난히 '붙어서'라는 글자가 굵게 볼드처리 되어있는데,

기존에 띄어서 입력을 받은 것에서 붙은 입력을 리스트로 저장하기 위해

split()이 아닌 strip()을 사용하여 리스트 형태로 만들 수 있다.

 

 

다음과 같이 현재의 수에서 넓게 탐색을 진행하면서

진행 방향에 현재의 수 + 1만큼을 해주게 되면,

마지막 수에는 지금까지 거쳐온 횟수인 15를 저장할 수 있게 된다.

 

import sys
from collections import deque
input = sys.stdin.readline

n,m = map(int, input().split())
maze = [list(map(int, input().strip())) for _ in range(n)]

dy = [0, 1, 0, -1]
dx = [1, 0, -1, 0]

def bfs(y, x):
  q = deque([(y, x)])
  while q:
    ey, ex = q.popleft()
    for k in range(4):
      ny = ey + dy[k]
      nx = ex + dx[k]
      if 0 <= ny < n and 0 <= nx < m and maze[ny][nx] == 1:
        maze[ny][nx] = maze[ey][ex] + 1
        q.append((ny, nx))
      
  return maze[n-1][m-1]

print(bfs(0,0))

 

미로는 상하좌우로 움직일 수 있기 때문에 총 4가지 방향을 주고,

4번의 반복을 돌면서 미로가 1일 때,

다음 위치 좌표에 현재 위치 + 1만큼을 할당해준다.

 

그리고나서 리스트는 0번째 인덱스부터 시작하기 때문에

n과 m에서 -1을 한 미로의 인덱스를 찾아 print하면 정답이 된다.

 

화이팅 💪