백준 - 레이저 통신 6087 (그래프, BFS, 골3)

문제 풀러가기

해당 문제는 C-C까지 레이저가 도달하기까지 설치해야하느 거울의 최소 개수를 구해야 한다.

문제를 처음 보았을 때 생각한 것은 C-C까지의 최단 거리를 구하는 문제로 생각했다. 하지만 다른 기본적인 BFS 문제와 다른 점은 방향을 꺽는 횟수를 최소화 해서 도달해야 한다는 점이었다. 그래서 BFS 문제를 풀 때 가지치기 하는 것이 중요한데, 초점을 맞춘 부분이 특정 지점에 몇 번만의 꺽어서 도달했는지 여부를 확인하는 것이였다. 코드를 보면 다음과 같았다.

해당 코드는 처음 제출 했던 코드였는데, 잘못된 코드였다. 코드를 보면 x, y, cost, dir은 차례대로 x, y 좌표, 몇 번 꺽었는지, 진행 방향을 나타낸다.

while dq:
    x, y, cost, dir = dq.popleft()

    for i in range(4):
        nx , ny = x + dirX[i], y + dirY[i]
        if 0 <= nx < H and 0 <= ny < W and MAPS[nx][ny] != '*':
        
            if dir == i:
                if check[nx][ny] > cost:
                    check[nx][ny] = cost
                    dq.append((nx,ny,cost,i))
            elif (dir + 2) % 4 != i:
                if check[nx][ny] > cost + 1:
                    check[nx][ny] = cost + 1
                    dq.append((nx,ny,cost+1,i))

이 코드가 틀린 이유는 이 테스트 케이스를 돌려보면 확인할 수 있는데,

3 4
..C
...
...
C*.

정답은 1이였지만 2가 출력되고 있던 것이다. (0,2) 위치에서 출발한 레이저가 도착 지점인 C가 있는 곳 위인 (2,0) 까지 1번만 꺽어서 잘 도달하고 있었으나, 실제로는 (2,0)에 도달한 방향이
<- 이 방향이 였던 것이다. 그래서 결과적으로 1번 더 꺽어야 도착 지점까지 올 수 있던 것이 었다.

따라서 단순히 몇 번 꺽는 것만 중요한 것이 아니라, 어떤 방향으로 왔는지도 같이 확인해야 한다는 것이다.

따라서 check배열에 각 방향 정보도 담아 확인을 진행했다.

import sys
from collections import deque

W, H = map(int,sys.stdin.readline().split())
MAPS = [list(sys.stdin.readline().strip()) for _ in range(H)]
check = [[[sys.maxsize,sys.maxsize,sys.maxsize,sys.maxsize] for _ in range(W)] for _ in range(H)]
dq = deque()
dirX = [0,-1,0,1]
dirY = [-1,0,1,0]

c = []
for i in range(H):
    for j in range(W):
        if MAPS[i][j] == 'C':
            c.append((i,j))


check[c[0][0]][c[0][1]][0] = 0
check[c[0][0]][c[0][1]][1] = 0
check[c[0][0]][c[0][1]][2] = 0
check[c[0][0]][c[0][1]][3] = 0

dq.append((c[0][0],c[0][1],0,0))
dq.append((c[0][0],c[0][1],0,1))
dq.append((c[0][0],c[0][1],0,2))
dq.append((c[0][0],c[0][1],0,3))

while dq:
    x, y, cost, dir = dq.popleft()

    for i in range(4):
        nx , ny = x + dirX[i], y + dirY[i]
        if 0 <= nx < H and 0 <= ny < W and MAPS[nx][ny] != '*':
            if dir == i: # 현재 진행 방향으로 
                if check[nx][ny][i] > cost:
                    check[nx][ny][i] = cost
                    dq.append((nx,ny,cost,i))
            elif (dir + 2) % 4 != i: # 90도 꺽기
                if check[nx][ny][i] > cost + 1:
                    check[nx][ny][i] = cost + 1
                    dq.append((nx,ny,cost+1,i))

print(min(check[c[1][0]][c[1][1]]))

1일 1알골 clear