백준 온라인 저지, 최단경로 / 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

힌트

W3sicHJvYmxlbV9pZCI6IjYwODciLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWI4MDhcdWM3NzRcdWM4MDAgXHVkMWI1XHVjMmUwIiwiZGVzY3JpcHRpb24iOiI8cD5cdWQwNmNcdWFlMzBcdWFjMDAgMSZ0aW1lczsxXHVjNzc4IFx1YzgxNVx1YzBhY1x1YWMwMVx1ZDYxNVx1YzczY1x1Yjg1YyBcdWIwOThcdWIyMDRcdWM1YjRcdWM5YzQgVyZ0aW1lcztIIFx1ZDA2Y1x1YWUzMFx1Yzc1OCZuYnNwO1x1YzljMFx1YjNjNFx1YWMwMCBcdWM3ODhcdWIyZTQuIFx1YzljMFx1YjNjNFx1Yzc1OCBcdWFjMDEgXHVjZTc4XHVjNzQwIFx1YmU0OCBcdWNlNzhcdWM3NzRcdWFjNzBcdWIwOTggXHViY2JkXHVjNzc0XHViYTcwLCBcdWI0NTAgXHVjZTc4XHVjNzQwICYjMzk7PGNvZGU+QzxcL2NvZGU+JiMzOTtcdWI4NWMgXHVkNDVjXHVjMmRjXHViNDE4XHVjNWI0IFx1Yzc4OFx1YjI5NCBcdWNlNzhcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPiYjMzk7PGNvZGU+QzxcL2NvZGU+JiMzOTtcdWI4NWMgXHVkNDVjXHVjMmRjXHViNDE4XHVjNWI0IFx1Yzc4OFx1YjI5NCBcdWI0NTAgXHVjZTc4XHVjNzQ0IFx1YjgwOFx1Yzc3NFx1YzgwMFx1Yjg1YyBcdWQxYjVcdWMyZTBcdWQ1NThcdWFlMzAgXHVjNzA0XHVkNTc0XHVjMTFjIFx1YzEyNFx1Y2U1OFx1ZDU3NFx1YzU3YyBcdWQ1NThcdWIyOTQgXHVhYzcwXHVjNmI4IFx1YWMxY1x1YzIxOFx1Yzc1OCBcdWNkNWNcdWMxOWZcdWFjMTJcdWM3NDQgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuIFx1YjgwOFx1Yzc3NFx1YzgwMFx1Yjg1YyBcdWQxYjVcdWMyZTBcdWQ1NWNcdWIyZTRcdWIyOTQgXHVhYzgzXHVjNzQwIFx1YjQ1MCBcdWNlNzhcdWM3NDQgXHViODA4XHVjNzc0XHVjODAwXHViODVjIFx1YzVmMFx1YWNiMFx1ZDU2MCBcdWMyMTggXHVjNzg4XHVjNzRjXHVjNzQ0IFx1Yzc1OFx1YmJmOFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViODA4XHVjNzc0XHVjODAwXHViMjk0IENcdWM1ZDBcdWMxMWNcdWI5Y2MgXHViYzFjXHVjMGFjXHVkNTYwIFx1YzIxOCBcdWM3ODhcdWFjZTAsIFx1YmU0OCBcdWNlNzhcdWM1ZDAgXHVhYzcwXHVjNmI4KCYjMzk7PGNvZGU+XC88XC9jb2RlPiYjMzk7LCAmIzM5Ozxjb2RlPlxcPFwvY29kZT4mIzM5OylcdWM3NDQgXHVjMTI0XHVjZTU4XHVkNTc0XHVjMTFjIFx1YmMyOVx1ZDVhNVx1Yzc0NCA5MFx1YjNjNCBcdWQ2OGNcdWM4MDRcdWMyZGNcdWQwYWMgXHVjMjE4IFx1Yzc4OFx1YjJlNC4mbmJzcDs8XC9wPlxyXG5cclxuPHA+XHVjNTQ0XHViNzk4IFx1YWRmOFx1YjliY1x1Yzc0MCBIID0gOCwgVyA9IDdcdWM3NzggXHVhY2JkXHVjNmIwXHVjNzc0XHVhY2UwLCBcdWJlNDggXHVjZTc4XHVjNzQwICYjMzk7PGNvZGU+LjxcL2NvZGU+JiMzOTssIFx1YmNiZFx1Yzc0MCAmIzM5Ozxjb2RlPio8XC9jb2RlPiYjMzk7XHViODVjIFx1YjA5OFx1ZDBjMFx1YjBjOFx1YjJlNC4gXHVjNjdjXHVjYWJkXHVjNzQwIFx1Y2QwOFx1YWUzMCBcdWMwYzFcdWQwZGMsIFx1YzYyNFx1Yjk3OFx1Y2FiZFx1Yzc0MCBcdWNkNWNcdWMxOGMgXHVhYzFjXHVjMjE4XHVjNzU4IFx1YWM3MFx1YzZiOFx1Yzc0NCBcdWMwYWNcdWM2YTlcdWQ1NzRcdWMxMWMgXHViNDUwICYjMzk7PGNvZGU+QzxcL2NvZGU+JiMzOTtcdWI5N2MgXHVjNWYwXHVhY2IwXHVkNTVjIFx1YWM4M1x1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHByZT5cclxuNyAuIC4gLiAuIC4gLiAuICAgICAgICAgNyAuIC4gLiAuIC4gLiAuXHJcbjYgLiAuIC4gLiAuIC4gQyAgICAgICAgIDYgLiAuIC4gLiAuIFwvLUNcclxuNSAuIC4gLiAuIC4gLiAqICAgICAgICAgNSAuIC4gLiAuIC4gfCAqXHJcbjQgKiAqICogKiAqIC4gKiAgICAgICAgIDQgKiAqICogKiAqIHwgKlxyXG4zIC4gLiAuIC4gKiAuIC4gICAgICAgICAzIC4gLiAuIC4gKiB8IC5cclxuMiAuIC4gLiAuICogLiAuICAgICAgICAgMiAuIC4gLiAuICogfCAuXHJcbjEgLiBDIC4gLiAqIC4gLiAgICAgICAgIDEgLiBDIC4gLiAqIHwgLlxyXG4wIC4gLiAuIC4gLiAuIC4gICAgICAgICAwIC4gXFwtLS0tLS0tXC8gLlxyXG4gIDAgMSAyIDMgNCA1IDYgICAgICAgICAgIDAgMSAyIDMgNCA1IDZcclxuPFwvcHJlPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgV1x1YzY0MCBIXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDEgJmxlOyBXLCBIICZsZTsgMTAwKTxcL3A+XHJcblxyXG48cD5cdWI0NThcdWM5ZjggXHVjOTA0XHViZDgwXHVkMTMwIEhcdWFjMWNcdWM3NTggXHVjOTA0XHVjNWQwIFx1YzljMFx1YjNjNFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YzljMFx1YjNjNFx1Yzc1OCBcdWFjMDEgXHViYjM4XHVjNzkwXHVhYzAwIFx1Yzc1OFx1YmJmOFx1ZDU1OFx1YjI5NCBcdWFjODNcdWM3NDAgXHViMmU0XHVjNzRjXHVhY2ZjIFx1YWMxOVx1YjJlNC48XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT48Y29kZT4uPFwvY29kZT46IFx1YmU0OCBcdWNlNzg8XC9saT5cclxuXHQ8bGk+PGNvZGU+KjxcL2NvZGU+OiBcdWJjYmQ8XC9saT5cclxuXHQ8bGk+PGNvZGU+QzxcL2NvZGU+OiBcdWI4MDhcdWM3NzRcdWM4MDBcdWI4NWMgXHVjNWYwXHVhY2IwXHVkNTc0XHVjNTdjIFx1ZDU1OFx1YjI5NCBcdWNlNzg8XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD4mIzM5Ozxjb2RlPkM8XC9jb2RlPiYjMzk7XHViMjk0IFx1ZDU2ZFx1YzBjMSBcdWI0NTAgXHVhYzFjXHVjNzc0XHVhY2UwLCBcdWI4MDhcdWM3NzRcdWM4MDBcdWI4NWMgXHVjNWYwXHVhY2IwXHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVjNzg1XHViODI1XHViOWNjIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIENcdWI5N2MgXHVjNWYwXHVhY2IwXHVkNTU4XHVhZTMwIFx1YzcwNFx1ZDU3NCBcdWMxMjRcdWNlNThcdWQ1NzRcdWM1N2MgXHVkNTU4XHViMjk0IFx1YWM3MFx1YzZiOCBcdWFjMWNcdWMyMThcdWM3NTggXHVjZDVjXHVjMTlmXHVhYzEyXHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4ifSx7InByb2JsZW1faWQiOiI2MDg3IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiTGFzZXJwaG9uZXMiLCJkZXNjcmlwdGlvbiI6IjxwPlRoZSBjb3dzIGhhdmUgYSBuZXcgbGFzZXItYmFzZWQgc3lzdGVtIHNvIHRoZXkgY2FuIGhhdmUgY2FzdWFsIGNvbnZlcnNhdGlvbnMgd2hpbGUgb3V0IGluIHRoZSBwYXN0dXJlIHdoaWNoIGlzIG1vZGVsZWQgYXMgYSBXIHggSCBncmlkIG9mIHBvaW50cyAoMSAmbHQ7PSBXICZsdDs9IDEwMDsgMSAmbHQ7PSBIICZsdDs9IDEwMCkuPFwvcD5cclxuXHJcbjxwPlRoZSBzeXN0ZW0gcmVxdWlyZXMgYSBzb3J0IG9mIGxpbmUtb2Ytc2lnaHQgY29ubmVjdGl2aXR5IGluIG9yZGVyIHRvIHN1c3RhaW4gY29tbXVuaWNhdGlvbi4gVGhlIHBhc3R1cmUsIG9mIGNvdXJzZSwgaGFzIHJvY2tzIGFuZCB0cmVlcyB0aGF0IGRpc3J1cHQgdGhlIGNvbW11bmljYXRpb24gYnV0IHRoZSBjb3dzIGhhdmUgcHVyY2hhc2VkIGRpYWdvbmFsIG1pcnJvcnMgKCYjMzk7XC8mIzM5OyBhbmQgJiMzOTtcXCYjMzk7IGJlbG93KSB0aGF0IGRlZmxlY3QgdGhlIGxhc2VyIGJlYW0gdGhyb3VnaCBhIDkwIGRlZ3JlZSB0dXJuLiBCZWxvdyBpcyBhIG1hcCB0aGF0IGlsbHVzdHJhdGVzIHRoZSBwcm9ibGVtLjxcL3A+XHJcblxyXG48cD5IIGlzIDggYW5kIFcgaXMgNyBmb3IgdGhpcyBtYXAuIFRoZSB0d28gY29tbXVuaWNhdGluZyBjb3dzIGFyZSBub3RhdGVkIGFzICYjMzk7QyYjMzk7czsgcm9ja3MgYW5kIG90aGVyIGJsb2NraW5nIGVsZW1lbnRzIGFyZSBub3RhdGVkIGFzICYjMzk7KiYjMzk7czo8XC9wPlxyXG5cclxuPHByZT5cclxuNyAuIC4gLiAuIC4gLiAuICAgICAgICAgNyAuIC4gLiAuIC4gLiAuXHJcbjYgLiAuIC4gLiAuIC4gQyAgICAgICAgIDYgLiAuIC4gLiAuIFwvLUNcclxuNSAuIC4gLiAuIC4gLiAqICAgICAgICAgNSAuIC4gLiAuIC4gfCAqXHJcbjQgKiAqICogKiAqIC4gKiAgICAgICAgIDQgKiAqICogKiAqIHwgKlxyXG4zIC4gLiAuIC4gKiAuIC4gICAgICAgICAzIC4gLiAuIC4gKiB8IC5cclxuMiAuIC4gLiAuICogLiAuICAgICAgICAgMiAuIC4gLiAuICogfCAuXHJcbjEgLiBDIC4gLiAqIC4gLiAgICAgICAgIDEgLiBDIC4gLiAqIHwgLlxyXG4wIC4gLiAuIC4gLiAuIC4gICAgICAgICAwIC4gXFwtLS0tLS0tXC8gLlxyXG4gIDAgMSAyIDMgNCA1IDYgICAgICAgICAgIDAgMSAyIDMgNCA1IDZcclxuPFwvcHJlPlxyXG5cclxuPHA+RGV0ZXJtaW5lIHRoZSBtaW5pbXVtIG51bWJlciBvZiBtaXJyb3JzIE0gdGhhdCBtdXN0IGJlIGluc3RhbGxlZCB0byBtYWludGFpbiBsYXNlciBjb21tdW5pY2F0aW9uIGJldHdlZW4gdGhlIHR3byBjb3dzLCBhIGZlYXQgd2hpY2ggaXMgYWx3YXlzIHBvc3NpYmxlIGluIHRoZSBnaXZlbiB0ZXN0IGRhdGEuPFwvcD5cclxuIiwiaW5wdXQiOiI8dWw+XHJcblx0PGxpPkxpbmUgMTogVHdvIHNwYWNlIHNlcGFyYXRlZCBpbnRlZ2VyczogVyBhbmQgSDxcL2xpPlxyXG5cdDxsaT5MaW5lcyAyLi5IKzE6IFRoZSBlbnRpcmUgcGFzdHVyZS48XC9saT5cclxuPFwvdWw+XHJcbiIsIm91dHB1dCI6Ijx1bD5cclxuXHQ8bGk+TGluZSAxOiBBIHNpbmdsZSBpbnRlZ2VyOiBNPFwvbGk+XHJcbjxcL3VsPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJFbmdsaXNoIn1d

접근 방법

- 다익스트라 최단경로 알고리즘을 활용해 현재 위치에서 상하좌우로 이동한다.
- 이때 *나 범위를 벗어나게 될 경우 거울 설치 개수를 하나 늘린다.
- 이후 다른 c에 도착한다면 해당 위치에서의 거울 설치 개수를 출력한다.

코드

# https://www.acmicpc.net/problem/6087
# 접근 방법
# 다익스트라 최단경로 알고리즘을 활용해 현재 위치에서 상하좌우로 이동한다.
# 이때 *나 범위를 벗어나게 될 경우 거울 설치 개수를 하나 늘린다.
# 이후 다른 c에 도착한다면 해당 위치에서의 거울 설치 개수를 출력한다.
def dijkstra():
    r, c = target[0]
    graph[r][c] = 0
    q = []
    for i in range(4):
        heapq.heappush(q, [0, r, c, i])
    direction = [[1, 0], [-1, 0], [0, 1], [0, -1]]
    while q:
        count, row, col, dir = heapq.heappop(q)
        if graph[row][col] not in ['.', '*'] and graph[row][col] < count:
            continue
        for i in range(4):
            dr, dc = direction[i]
            num = count + 1
            if i == dir:
                num = count
            if 0<=row+dr= num):
                    graph[row+dr][col+dc] = num
                    heapq.heappush(q, [num, row+dr, col+dc, i])  
                
import heapq
w, h = map(int, input().split())
graph = [[x for x in input()] for _ in range(h)]
target = []
for r in range(h):
    for c in range(w):
        if graph[r][c] == 'C':
            target.append([r, c])
dijkstra()
r, c = target[1]
print(graph[r][c])