[Python][백준 17836][BFS] 공주님을 구해라! - 컴도리돌이

반응형

17836번: 공주님을 구해라!

---

풀이 과정 

1. bfs로 해결을 하였다. q에는 x, y 좌표 값과 이동 시간, 무기를 갖고 있는지 확인용 key 값을 1x4 배열로 넣어줬다.

2. 주의할 점은 방문 표시를 n x m 행렬로 해주면 안 된다. n x m으로 방문 표시를 하면 용사가 무기를 가질 때, 용사가 무기가 없어서 우회했던 경로를 다시 방문할 수 없기 때문에 시간 초과가 발생할 것이다.

3. q에서 pop을 할 때 x, y 값이 공주가 있는 곳(n-1, m-1)으로 올 경우 time이 k보다 작을 때 탐색으로 종료시킨다. 하지만 time이 k보다 클 경우 굳이 탐색할 필요 없기 때문에 continue를 해주었다.

---

풀이 코드

import sys,collections ; input = sys.stdin.readline
n,m,k = map(int,input().split())
board = [list(map(int,input().split())) for _ in range(n)]
visited = [ [ [False for _ in range(m)] for _ in range(n)] for _ in range(2)]
dx,dy = [0,0,-1,1],[-1,1,0,0]
q = collections.deque([[0,0,0,0]]) # x,y,move,key
visited[0][0][0] = True
while q :
  x,y,move,key = q.popleft()
  if x == n-1 and y == m-1 and move <= k:
    print(move)
    break
  if move > k :
    continue
  for i in range(4) :
    nx = x + dx[i]
    ny = y + dy[i]
    if 0<= nx < n and 0 <= ny < m and not visited[key][nx][ny] :
      if key == 1 :
        visited[key][nx][ny] = True
        q.append([nx,ny,move+1,key])
      else :
        if board[nx][ny] == 0 :
          visited[key][nx][ny] = True
          q.append([nx,ny,move+1,key])
        elif board[nx][ny] == 2 :
          visited[1][nx][ny] = True
          q.append([nx,ny,move+1,1])
        else :
          continue
else :
  print("Fail")