🔦 문제 링크
✍️ 나의 풀이
처음엔 데크의 앞으로 넣어서 거울쓰는 갯수가 적은 것부터 방문하려고 했으나 실패했다. 다른 방향으로 왔을 때 빠른 경우가 존재하기 때문인 것 같다.
이 문제의 핵심아이디어는 한 방향으로 갈 수 있는 곳을 모두 방문하는 것이다. 그렇게 하면 그 순간에 방문할 수 있는 곳을 모두 최소로 방문한다.
- 상, 하, 좌, 우로 방문을 하되 벽을 만날 때까지 검사한다.
- 같은 방향은 모두 체크되어 있으므로 새로운 검사시에는 무조건 거울이 필요하다.
- 중간에 목적지를 만났다고 BFS를 끝내서는 안된다. 다른 길이 최적값을 만들 수도 있기 때문이다.
🛠 나의 코드
# 어떤 것의 최솟값을 구할 것인가??? -> 설치해야하는 거울의 최솟값 -> dist의 원소
from collections import deque
dx = (-1, 1, 0, 0)
dy = (0, 0, -1, 1)
def BFS(sx, sy):
q = deque()
q.append((sx, sy))
while q:
x, y = q.popleft()
for k in range(4):
nx, ny = x + dx[k], y + dy[k]
# 다른 BFS와 다른 부분
while 0 <= nx < h and 0 <= ny < w and arr[nx][ny] != '*':
if not dist[nx][ny]:
dist[nx][ny] = dist[x][y] + 1 # x, y 의 값에 1을 더한 것이다.
q.append((nx, ny))
nx, ny = nx + dx[k], ny + dy[k]
w, h =map(int, input().split())
arr = [list(input()) for _ in range(h)]
dist = [[0] * w for _ in range(h)]
# C의 위치 확인
c_pos = []
for i in range(h):
for j in range(w):
if arr[i][j] == 'C':
c_pos.append((i, j))
BFS(c_pos[0][0], c_pos[0][1])
print(dist[c_pos[1][0]][c_pos[1][1]]-1)
📝 정리
- 틀린 코드!
while 0 <= nx < h and 0 <= ny < w and check[nx][ny] == 0 and arr[nx][ny] != '*':
check[nx][ny] = check[tx][ty] + 1
q.append((nx, ny))
nx, ny = nx + dx[k], ny + dy[k]틀린 코드는 check배열이 이미 방문했으면 반복을 멈추도록 했다.
하지만 1112000 같은 경우에 1이 2를 뛰어넘어 0의 값을 바꾸도록 해야한다. 왜냐하면 거울을 쓴 최솟값을 구하는 것이기 때문에 벽을 만난게 아니라면 계속해서 진행해야한다.
여기서는 큐가 진행될수록 거울의 수가 늘어날 수 밖에 없기 때문에 벽을 만날 때까지 진행시켜주면 되지만 거울의 수가 뒤죽박죽이라면 거울의 수가 작아질 경우에만 갱신해주면 된다.
- 움직인 횟수가 아니기 때문에 목적지에 가장 먼저 도착했다고 최적값이 아니다.
- 값이 더 작거나 같은 값으로 갱신되지 않으면 넣지 않는 것이 Check역할을 대신한다.
🎈 참고
Go Go