새로운 블로그로 이전 작업을 진행하고 있어 포스트가 새로 작성되고 있지 않습니다.

빠른 시일 내에 새로운 블로그로 인사드리겠습니다.

새로운 블로그 : https://unho.vercel.app/

본문 바로가기
알고리즘 문제풀이/Python

[백준] 6087 레이저 통신

by 언호 2022. 7. 17.

📖 문제


🧑🏻‍💻 풀이 과정

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번: 레이저 통신

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

www.acmicpc.net

 

 

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

댓글