[We-Co] 미로 탐색 - 백준 2178번

안녕하세요. 위기의 코딩맨입니다.

오늘은 백준 2178번 문제 미로 탐색 문제를 풀어보도록 하겠습니다.

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

2178번: 미로 탐색

 

문제를 이해하셨다면 input으로 데이터를 받아야합니다.

4 6
101111
101010
101011
111011

4,6을 A,B로 받아주도록 합니다.

 

A, B = map(int,input().split())  

 

그리고 밑에 좌표에 해당 값들을 넣어주어야 합니다.

 

graph = [] 
for _ in range(A):
  graph.append(list(map(int, input())))

 

graph를 출력해보면 해당 값이 입력된 것을 확인할 수 있습니다.

[[1, 0, 1, 1, 1, 1],

[1, 0, 1, 0, 1, 0], 

[1, 0, 1, 0, 1, 1],

[1, 1, 1, 0, 1, 1]]

다음으로 좌표 이동하기 위한 상하좌우 리스트를 만들어 주도록 합니다.

xd = [-1,1,0,0]
yd = [0,0,-1,+1]

 

해당 문제는 BFS 방식을 사용하여 풀어보도록 하겠습니다.

 

from collections import deque

 

def BFS(x,y):
  que = deque()
  que.append((x,y))
  while que:
    x, y = que.popleft()
    for i in range(4):
      nx = x + xd[i]
      ny = y + yd[i]
      if nx < 0 or ny < 0 or nx >= A or ny >= B:
        continue
      if list_[nx][ny] == 0:
         continue
      if list_[nx][ny] == 1:
        list_[nx][ny] = list_[x][y] + 1
        que.append((nx,ny))  
  return list_[-1][-1] 

 

하나씩 설명드리면 que를 사용하여 BFS를 구현했습니다.

que에 처음 시작 좌표를 넣어주고

while 루프를 que가 비었을 때 종료되는 조건으로 생성하고x와 y를 que.popleft()를 사용하여 데이터를 넣어주고상,하,좌,우 4번의 for문을 통해서경로를 탐색하게 됩니다.이동경로를 벗어날 경우와 해당 값이 0일때는 다음 루프로 넘어가도록 하고1일 경우에 list[nx][ny]에 직전의 값에 +1 값을 넣어주고조건이 벗어나고 return 값에 마지막 값을 넣어주었습니다.

 

결과 값

리스트의 마지막 값에는 이동경로의 마지막 값이 들어가게 되어 해당 문제의 정답 15가 들어있습니다.