[백준] 6087 레이저 통신

📖 문제

---

🧑🏻‍💻 풀이 과정

1) 문제 접근 및 이해

출발점에서 4가지 방향으로 진행을 시키고, 좌표에 도달하기에 필요한 거울의 개수를 기록하는 배열을 생성하였습니다.

큐를 이용하여 현재 좌표, 다음 진행 방향, 거울 사용 개수를 하나의 묶음으로 보관하였고, 탐색하였습니다.

그리고 방향 전환이 발생하는 경우에 거울 사용 개수에 1을 추가하였습니다.

2) 알고리즘

• BFS

3) 풀이 코드

사용 언어 - Python

import sys
from collections import deque
sys.stdin = open('input.txt')

def solution(start):
    q = deque()
    for k in range(4):                              # 시작 좌표는 4가지 방향으로 시작할 수 있음
        q.append((start[0], start[1], k, 0))        # 좌표, 진행 방향, 거울 사용 개수
    
    while q:
        y, x, d, ans = q.popleft()
        r = y + dr[d]                               # 진행 방향을 통해 다음칸 좌표
        c = x + dc[d]

        # 범위내의 좌표이고, 벽면이 아니며, 거울 사용 횟수가 같거나 적을때만
        if 0 <= r < H and 0 <= c < W and board[r][c] != '*' and visited[r][c] >= ans:
            visited[r][c] = ans                     # 거울 사용 횟수 기록
            for k in [-1, 0, 1]:                    # 진행 방향의 왼쪽, 유지, 오른쪽
                nd = (d+k) % 4                      # 다음 새로운 방향
                if k:                               # 새로운 진행 방향이라면 거울 사용 추가
                    q.append((r, c, nd, ans+1))
                else:                               # 방향 유지라면 거울 사용 안함
                    q.append((r, c, nd, ans))
                
dr = [-1, 0, 1, 0]      # 위 오른쪽 아래 왼쪽
dc = [0, 1, 0, -1]

W, H = map(int ,sys.stdin.readline().split())                       # 열, 행의 개수
board = [list(sys.stdin.readline().strip()) for _ in range(H)]      # 지도의 정보
visited = [[1e10] * W for _ in range(H)]      # 각 좌표 도달 필요 거울 개수, 진행방향

points = []                             # 시작, 도착 좌표

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

solution(points.pop())                  # 탐색

end = points.pop()                      # 도착 좌표
print(visited[end[0]][end[1]])          # 목적지 도착에 필요한 거울의 개수

---

🔗 문제 링크

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

6087번: 레이저 통신

 

 

※ 오류 및 오타, 다른 의견이 있는 경우 댓글을 남겨주시면 감사하겠습니다