레이저 통신 (6087번) - 백준 (BOJ)

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

6087번: 레이저 통신

 

백준 - 레이저 통신 (Laserphones) (6087번)

 

난이도 : Gold 3

알고리즘&자료구조 : BFS (너비 우선 탐색) & Simulation (구현)

---

★ 핵심 Idea ★

 

첫 번째 소부터 특정 좌표까지 통신하는데 필요한 거울의 개수를 BFS로 구하면서,

두 번째 소까지 이동하면 된다.

 

 

 

< 전체 코드 >

 

import sys
input = sys.stdin.readline


class Pasture():
    def __init__(self, W, H):
        board = [list(input().rstrip()) for _ in range(H)]
        queue = []
        for h in range(H):
            for w in range(W):
                if board[h][w] == 'C':
                    queue.append((h, w))
        goal = queue.pop()

        dd = ((1, 0), (-1, 0), (0, 1), (0, -1))
        cnt = flag = 0
        tmp = []
        while True:
            while queue:
                ch, cw = queue.pop()
                for i in range(4):
                    dh, dw = dd[i]
                    ph, pw = ch+dh, cw+dw
                    while 0 <= ph < H and 0 <= pw < W:
                        if (ph, pw) == goal:
                            flag = True
                            self.mirrors = cnt
                            break
                        if board[ph][pw] == '.':
                            board[ph][pw] = cnt
                            tmp.append((ph, pw))
                            ph, pw = ph+dh, pw+dw
                        elif board[ph][pw] == cnt:
                            ph, pw = ph+dh, pw+dw
                        else:
                            break
                    if flag:
                        break
                if flag:
                    break
                board[ch][cw] = '*'
            if flag:
                break
            queue = tmp
            tmp = []
            cnt += 1


if __name__ == '__main__':
    pasture = Pasture(*map(int, input().split()))
    print(pasture.mirrors)