[BFS] 1175번 배달

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

알고리즘

• BFS

풀이

포인트

• 하나의 state을 나타내는 조건들이 여러개라는 점

BFS

문제에서 주어진 조건들이 여러개라 이를 state로 연관하고 그에 맞게 프로그래밍을 하는게 약간 어려운 문제이다. 먼저 주의해야하는 조건을 정리해보자.

• 선물이 2개이고 이를 모두 배달하기 전까지 배달은 끝나지 않는다. 두 개의 선물을 각각 A,B라고 할 때, 아래 네 개의 상태가 존재한다.
  • A만 배달한 상태
  • B만 배달한 상태
  • 두 개 모두 배달하지 않은 상태
  • 둘 모두 배달한 상태
• 같은 방향으로 두 번 연속 이동할 수 없다. 따라서 (i,j)를 방문했을 때, 어느 방향을 보고 있는지에 따라서 동,서,남,북 네 개의 상태가 존재한다.

이런 문제 의식을 가지고 bfs 테이블을 $n \times m \times 4 \times 4$로 초기화하였다.

visited = [[[[-1]*4 for _ in range(4)] for _ in range(m)] for _ in range(n)]

$visited[i][j][d][state]$는, (i,j)를 방문했을 때 d 방향을 바라보고 있고 현재 상태는 state임을 의미한다. d는 0에서 3의 값을 가지고 dx,dy의 0번째 ~ 3번째 값을 의미한다 (북,동,남,서) 또한 state는 0에서 3의 값을 가지고 각각 (A 선물만 배달한 경우, B 선물만 배달한 경우, 둘 모두 배달하지 않은 경우, 둘 모두 배달한 경우)를 의미한다. 두 선물 중 하나만 배달한 경우를 앞에 배치한 이유는, 다음에 방물할 곳에 선물이 있다면 그 선물이 이미 배달한 것인지 그렇지 않은 것인지 빠르게 판단하기 위함이다.

[Source Code]

from collections import deque
n,m = map(int,input().split())
a = [input() for _ in range(n)]
c = []
for i in range(n):
    for j in range(m):
        if a[i][j] == 'S':
            x,y = i,j
        if a[i][j] == 'C':
            c.append((i,j))
visited = [[[[-1]*4 for _ in range(4)] for _ in range(m)] for _ in range(n)]
dx = [-1,0,1,0]
dy = [0,1,0,-1]
q = deque()
for i in range(4):
    visited[x][y][i][2] = 0
    q.append((x,y,i,2))
ans = -1
while q:
    x,y,d,state = q.popleft()
    if state == 3:
        ans = visited[x][y][d][state]
        break
    for i in range(4):
        if i == d:
            continue
        nx,ny = x+dx[i],y+dy[i]
        if 0 <= nx < n and 0 <= ny < m and a[nx][ny] != '#':
            # 방문할 곳에 선물이 있다면,
            if a[nx][ny] == 'C':
                index = c.index((nx, ny))
                # 선물을 하나도 배달하지 않았고 처음 방문한다면, state를 index로 업데이트.
                # 선물 배달 -> index 선물 배달이므로.
                if state == 2 and visited[nx][ny][i][index] == -1:
                    visited[nx][ny][i][index] = visited[x][y][d][state] + 1
                    q.append((nx,ny,i,index))
                # 선물을 하나 배달했고 (state in [0,1])
                # 배달한 선물이 현재 방문한 곳의 선물과 다르다면 (state != index)
                # 선물을 모두 배달한 것이니까 state를 3으로 업데이트 함.
                elif state in [0,1] and state != index and visited[nx][ny][i][3] == -1:
                    visited[nx][ny][i][3] = visited[x][y][d][state] + 1
                    q.append((nx, ny, i, 3))
            else:
                # 방문한 곳이 선물이 아니라면 현재 state를 그대로 업데이트 해줌.
                if visited[nx][ny][i][state] == -1:
                    visited[nx][ny][i][state] = visited[x][y][d][state] + 1
                    q.append((nx,ny,i,state))
print(ans)