[BOJ 6087] 레이저 통신 - Python 풀이

링크: https://www.acmicpc.net/problem/6087

 

문제

 

크기가 1×1인 정사각형으로 나누어진 W×H 크기의 지도가 있다. 지도의 각 칸은 빈 칸이거나 벽이며, 두 칸은 'C'로 표시되어 있는 칸이다.

'C'로 표시되어 있는 두 칸을 레이저로 통신하기 위해서 설치해야 하는 거울 개수의 최솟값을 구하는 프로그램을 작성하시오. 레이저로 통신한다는 것은 두 칸을 레이저로 연결할 수 있음을 의미한다.

레이저는 C에서만 발사할 수 있고, 빈 칸에 거울('/', '\')을 설치해서 방향을 90도 회전시킬 수 있다. 

아래 그림은 H = 8, W = 7인 경우이고, 빈 칸은 '.', 벽은 '*'로 나타냈다. 왼쪽은 초기 상태, 오른쪽은 최소 개수의 거울을 사용해서 두 'C'를 연결한 것이다.

 

7 . . . . . . .         7 . . . . . . .
6 . . . . . . C         6 . . . . . /-C
5 . . . . . . *         5 . . . . . | *
4 * * * * * . *         4 * * * * * | *
3 . . . . * . .         3 . . . . * | .
2 . . . . * . .         2 . . . . * | .
1 . C . . * . .         1 . C . . * | .
0 . . . . . . .         0 . \-------/ .
  0 1 2 3 4 5 6           0 1 2 3 4 5 6

 

입력

첫째 줄에 W와 H가 주어진다. (1 ≤ W, H ≤ 100)

둘째 줄부터 H개의 줄에 지도가 주어진다. 지도의 각 문자가 의미하는 것은 다음과 같다.

• .: 빈 칸
• *: 벽
• C: 레이저로 연결해야 하는 칸

'C'는 항상 두 개이고, 레이저로 연결할 수 있는 입력만 주어진다.

 

출력

첫째 줄에 C를 연결하기 위해 설치해야 하는 거울 개수의 최솟값을 출력한다.

 

예제 입력 1

7 8
.......
......C
......*
*****.*
....*..
....*..
.C..*..
.......

예제 출력 1

3

 

코드

import sys
import heapq

W, H = map(int, sys.stdin.readline().split())
grid = [sys.stdin.readline().rstrip() for _ in range(H)]
visited = [[False] * W for _ in range(H)]
dx, dy = [-1, 0, 1, 0], [0, -1, 0, 1]
s_x, s_y, e_x, e_y = -1, -1, -1, -1
result = sys.maxsize

# 출발 지점인 s_x, s_y와 도착 지점인 e_x, e_y를 설정해주는 부분
def init():
    global s_x, s_y, e_x, e_y
    pos = []
    
    for i in range(H):
        for j in range(W):
            if grid[i][j] == "C":
                pos.append(i)
                pos.append(j)
            if len(pos) == 4: break
        if len(pos) == 4: break
    
    s_x, s_y, e_x, e_y = pos

def in_range(x,y):
    return 0 <= x < H and 0 <= y < W

def can_go(x,y):
    if not in_range(x, y): return False
    if visited[x][y]: return False
    if grid[x][y] == "*": return False
    else: return True

def dijkstra():
    global result

    # heap으로 사용되는 변수 q에는 (cnt, dist, x, y, z)가 저장됨
    # cnt: 방향을 전환한 횟수
    # dist: 출발지점(s_x, s_y)로부터의 거리
    # x, y, z: x좌표, y좌표, 직전 좌표에서의 방향
    q = [(0, 0, s_x, s_y, -1)]
    while q:
        cnt, dist, x, y, z = heapq.heappop(q)
        
        if x == e_x and y == e_y: 
            result = cnt
            break

        visited[x][y] = True
        for i in range(4):
            new_x, new_y = x+dx[i], y+dy[i]
            if can_go(new_x, new_y):
                if z != -1 and z != i:
                    heapq.heappush(q, (cnt+1, dist+1, new_x, new_y, i))
                else: 
                    heapq.heappush(q, (cnt, dist+1, new_x, new_y, i))     
                
init()        
dijkstra()
print(result)

 

결과

 

풀이

처음에는 평범한 bfs를 사용하여 풀려고 하다가 cnt, 즉 방향을 전환한 횟수가 적은 순서대로 정렬하는 자료구조가 필요할 것 같아서 heapq를 사용하게 되었고 다익스트라와 유사한 알고리즘이 됨.

거리를 기준으로 가까운 순서대로 방문하는 것이 아니라 구하고자 하는 답인 방향 전환이 적은 순서대로 방문하는 것이 관건인 문제였음.

골드3 짜리 문제를 답 안보고 풀어서 뿌듯하다ㅎㅎ