[백준 - Python] 6087 - 레이저 통신

0.  문제 링크

 

 

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

6087번: 레이저 통신

 

이전 풀이

 

2023.02.03 - [Computer Science/알고리즘] - [백준 - Python] 6087 - 레이저 통신

[백준 - Python] 6087 - 레이저 통신

---

1.  풀이 방법

 

 

이전 풀이와 다르게 풀었음.

알고리즘은... 딱히 정의를 못하겠음..

굳이 정하자면 다익스트라?

 

1. 우선 빈 칸이라면 무조건 앞으로 계속해서 나아가야 함.
2. 빈칸이라면 힙에다가 다시 넣음. 그리고 방문 표시를 함 -> 방문 표시는 수평/수직 방향에 대해 처리하였음.
3. 힙의 기준은 사용한 거울의 개수를 기준으로 넣었음.
4. 또한 매 칸마다 사용한 거울의 개수를 집어넣었음.
   1. 빈 칸에 방문했는데, 기존의 거울 개수보다 적다면 방문함.
   2. 빈 칸에 방문했는데, 기존의 거울 개수와 같다면 수평/수직 방향에서 방문한 적이 없다면 방문함.

---

2.  코드

 

 

import sys
import heapq
input = sys.stdin.readline


def updateCntMaps(cnt, y, x):
    # 직선으로 쭉 나아감
    for i in range(4):      # 4방향으로
        dirY, dirX = dir[i]
        curY, curX = y, x
        while True:     # 쭉 나아감
            nextY, nextX = curY + dirY, curX + dirX
            if 0 <= nextY < h and 0 <= nextX < w:
                match maps[nextY][nextX]:
                    case '.':       # 빈 칸
                        if cntMaps[nextY][nextX] > cnt or \
                        (cntMaps[nextY][nextX] == cnt and chkMaps[i % 2][nextY][nextX] == False):        # 만약 기존의 거울 개수보다 적거나 같게 사용한다면
                            cntMaps[nextY][nextX] = cnt
                            chkMaps[i % 2][nextY][nextX] = True        # 방문 표시
                            heapq.heappush(hq, (cnt, nextY, nextX))
                            curY, curX = nextY, nextX       # 한 쪽으로 쭉 나아가기 위해
                        else:
                            break
                    case '*':
                        break
                    case 'C':
                        print(cnt)
                        exit(0)
            else:
                break


if __name__ == "__main__":
    w, h = map(int, input().split())
    maps = [list(input().strip()) for _ in range(h)]
    cntMaps = [[sys.maxsize] * w for _ in range(h)]      # 거울의 개수 체크
    chkMaps = [[[False]  * w for _ in range(h)] for _ in range(2)]      # 방문 체크, [0]은 수직, [1]은 수평
    hq = []
    dir = [[1, 0], [0, 1], [-1, 0], [0, -1]]

    for i in range(h):
        for j in range(w):
            if maps[i][j] == 'C':
                heapq.heappush(hq, (-1, i, j))
                maps[i][j] = '*'        # 벽으로 만듬

                # 다익스트라 알고리즘
                while hq:
                    cnt, y, x = heapq.heappop(hq)
                    updateCntMaps(cnt + 1, y, x)        # 벽을 만난 것이므로 +1해서 넣어줌

---

3.  마무리