[Python Algorithm] 레이저 통신 BOJ #6087

문제

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

6087번: 레이저 통신

 

내 문제 풀이

import sys
import math

w, h = map(int, sys.stdin.readline().strip().split())
table = []
dx = [0, 0, -1, 1]
dy = [-1, 1, 0, 0]
points = [] # 'C'의 위치 (처음 입력받는 위치를 시작점, 나중에 입력받는 위치를 도착점으로 설정함)

for i in range(h):
    now = list(sys.stdin.readline().strip())
    for j in range(w):
        if now[j] == 'C':
            points.append((i, j))
    table.append(now)

def bfs(x, y):
    visited = [[[math.inf] * 4 for _ in range(w)] for _ in range(h)] # 방문 체크
    queue = [] # 탐색할 위치의 정보 (행, 열, 방향)
    idx = 0

    # 본격적으로 탐색 전 queue에 가장 먼저 탐색을 시작할 위치들 추가
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if nx < 0 or ny < 0 or nx >= h or ny >= w or table[nx][ny] == '*':
            continue
        queue.append((nx, ny, i)) # i값을 통해 그 전까지 어떤 방향으로 움직였는지를 알 수 있게 함
        visited[nx][ny][i] = 0

    while idx < len(queue):
        (x, y, direct) = queue[idx]
        idx += 1

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if nx < 0 or ny < 0 or nx >= h or ny >= w or table[nx][ny] == '*':
                continue

            cnt = visited[x][y][direct] # 이전 자리의 방향 값을 통해 거울을 추가해야 하는지 정하기 위함
            if (direct <= 1 and i > 1) or (direct > 1 and i <= 1):
                cnt += 1

            # 방문한적 없는 자리일 경우, 거울 개수 그대로 저장 / 방문한적 있을 경우 더 작은 값으로 갱신
            if visited[nx][ny][i] == -1:
                visited[nx][ny][i] = cnt
                queue.append((nx, ny, i))
            elif visited[nx][ny][i] > cnt:
                visited[nx][ny][i] = cnt
                queue.append((nx, ny, i))

    # 도착 지점에 저장된 거울 개수 중 가장 작은 수 반환
    return min(visited[points[1][0]][points[1][1]])

# 시작 지점 좌표 넣어서 bfs 함수 호출
print(bfs(points[0][0], points[0][1]))

👉 BFS 문제로, 각 자리마다 네방향으로의 거울 개수를 고려해주면 된다.

 

[ 문제 분석 ]

좌표값 연산을 통해 탐색이 필요한 자리를 찾고, queue에 추가해주어 더이상 탐색할 자리가 없을 때까지
반복해주어야 하며, 방문 체크를 통해 필요없는 중복을 피해야 한다는 점은 일반적인 BFS 문제들과 같다.
그러나 이 문제는 일반적인 BFS 문제들과 가장 큰 두 가지 차이점이 있다.
(1) 방문 체크를 하되, 중복을 피하기 위함이 아니라 적절히 최솟값을 갱신해 주기 위함이라는 것
(2) 방문 체크 시 True, False가 아니라, 동서남북 모든 경우의 수를 고려하여 값을 저장해야 한다는 것
이러한 특징을 잘 생각하여 문제를 풀이해주어야 한다.

 

[ 풀이 설명 ]

• 주어진 지도 정보를 table 리스트에 저장해주었고, 'C' 발견 시 그 좌표값을 point 리스트에 저장했다.
  따라서 이 point 리스트는 'C'의 시작점과 도착점에 대한 정보를 가지게 된다.
  (bfs 함수 호출 시 시작점 좌표를 파라미터로 전달하고, bfs 함수 반환 시에는 도착점 좌표를 이용한다.)
• bfs 함수가 실행되면 visited, queue, idx를 생성한다.
  visited는 방문 체크를 하기 위함인데, 3중 리스트로 만들어서 가장 말단에는
  동서남북 네 방향으로의 모든 거울의 개수에 대한 경우의 수를 저장할 수 있게 하였다.
  queue는 앞으로 탐색이 필요한 좌표들에 대한 값을 저장하기 위해 생성했고,
  idx는 queue 리스트를 돌면서 순서대로 탐색을 돕기 위해 선언했다. (deque 사용해도 ok)
• while을 통해 본격적으로 탐색을 시작하기 전에, 가장 먼저 탐색할 자리들을 queue에 추가했다.
  시작점의 역할을 하는 'C'의 동서남북에 위치하는 좌표들이 이에 해당되는데,
  지도의 범위를 벗어나거나 벽이 아닐 경우에는 모두 queue에 추가했고,
  모든 방향에서 아직 거울은 사용하지 않았으므로 visited에는 0을 저장했다.
• while 안에서는 idx 값에 따라 현재 순서의 queue 인덱스를 x, y, direct로 받아왔다.
  for문을 통해 4번 반복하며 현재 자리의 네가지 방향을 고려해주었는데,
  마찬가지로 지도의 범위를 벗어나거나 벽이 있을 경우는 예외처리했다.
• 여기서 생각해주어야 할 것은, 새롭게 탐색을 고려하는 좌표(nx, ny)로 가는 방향이
  그 전에 이동하던 방향과 같은지, 다른지를 판단해주어야 한다는 것이다.
  내 코드의 경우 dx, dy 리스트를 확인하면 visited[x][y][direct]에서 direct 인덱스가
  0, 1일 경우에는 수직으로 이동, 2, 3일 경우에는 수평으로 이동했왔음을 알 수 있다.
  => direct가 1이하이며 i가 2 이상일 경우, 혹은 direct가 2이상이며 i가 1 이하일 경우에는
  그 전과 다른 방향으로 나아가고자 하는 것이므로, cnt를 1 키워준다. (거울 추가)
• 그리고 visited의 해당 인덱스에 -1이 저장되어있다면 방문한 적이 없는 자리이므로 cnt를 그대로 추가,
  해당 인덱스에 cnt보다 큰 값이 저장되어있다면 현재의 cnt 값으로 갱신해주었다.
  (거울을 최소로 사용하는 것이 목적이므로 계속하여 최솟갑으로 갱신)
• queue에 있는 모든 좌표를 탐색했다면 도착 지점 좌표의 visited 중 가장 작은 값을 반환한다.

 

💡 피드백

• 예외도 굉장히 많고 고려해줄 부분이 많아서 아주 오래 걸렸던 문제다.
  그래도 덕분에 BFS를 더 잘 알게 된 듯