[백준 1175번] 배달 (Python3)

import sys,collections
input = sys.stdin.readline
dy = [1,-1,0,0]; dx = [0,0,1,-1]

def BFS():
  visited = [[[[0]*M for i in range(N)] for i in range(5)] for i in range(3)]
  dq = collections.deque([(*start,0,0,4)])
  while dq:
    y,x,t,bit,d = dq.popleft()
    if visited[bit][d][y][x]:
      continue
    visited[bit][d][y][x] = 1
    if type(board[y][x])==int:
      bit |= 1<<board[y][x]
    if bit==3:
      return t
    for i in range(4):
      if i==d:
        continue
      y1,x1 = y+dy[i],x+dx[i]
      if N>y1>=0 and M>x1>=0 and board[y1][x1] != "#":
        dq.append((y1,x1,t+1,bit,i))
  return -1      

N,M = map(int,input().split()); board = [[*input().strip()] for i in range(N)]

c = 0
for y in range(N):
  for x in range(M):
    if board[y][x] == "S":
      start = (y,x)
    if board[y][x] == "C":
      board[y][x] = c
      c += 1
print(BFS())

간단한 BFS 문제.

하지만 visited 처리를 다양한 변수로 하는 것에 익숙지 않으면 푸는데 어려움을 겪을 수 있다.

 

핵심은 visited 배열을 어떻게 만드느냐이다.

일단 이 문제는 방향 변수가 매우 중요하다. 어떤 지점을 이미 방문했더라도, 어느 방향에서 도착했느냐에 따라 다음에 갈 수 있는 위치가 달라지기 때문이다. 따라서 이미 방문한 지점이더라도 다른 방향에서 도착했다면 방문해주어야한다.

또 어떤 선물을 배달했느냐도 중요하다. 이미 방문한 지점이더라도, 선물 하나를 배달했다면, 다시 그 지점을 지나서 다른 선물을 배달하기 위해 이동해야한다.

 

풀이를 설명하면,

1. 시작지점과 선물을 찾는다. 시작지점은 좌표를 저장하고, 선물은 찾은 순서대로 0, 1로 저장한다.

2. visited 배열을 4차원 배열로 만든다. 이때 visited[bit][d][y][x]에서 bit는 배달한 선물을 저장하는 변수, d는 이동한 방향을 의미한다. (즉, bit와 d가 다르다면 이미 방문한 지점도 방문하는 것이다)

3. 선물의 위치에 도착하면, bit에 선물의 번호를 저장한다.

4. bit가 3이 된다면 (이진법으로 11, 즉 모든 선물 배달 완료) 이동거리를 출력한다.

 

 

여담) 이 문제의 숏코딩 순위 1위가 되었다.