[BOJ]2151 - 거울 설치(Python/BFS)

🌱 발상 🌱

1️⃣ BFS 로 풀어도 되나? DFS 로 풀자 → 그것은 틀렸습니다

너비 우선 탐색을 하자니 한 거울을 두 번 사용하는 경우가 마음에 걸렸음. 만약 [2,2] 위치에서 45도 짜리 거울을 썼다면 돌고 돌아 다시 [2,2]에 방문했을 때도 똑같이 45도 짜리 거울을 써야 하는 것 아닌가? 그래서 [2,2] 에 놓인 거울의 방향을 표시해줘야 한다면 기존에 어떻게 사용했는지를 기억해야 한다고 생각했고 BFS로 돌리기엔 비효율적 + 큐에 각 거울 배치를 넣어주자니 메모리초과가 뻔해서 DFS 를 써야 한다고 생각했음

하지만 그것은 틀렸습니다.

한심좌 짤방이 등장하면 적절할 듯 싶음. 느낌표(!) 영역은 거울방향을 조절할 수 있고, 돌고 돌아서 재방문했을 때 출구에 도달한다면 거울을 더 적게 사용할 수 있는 오른쪽 배치가 답일 것. 따라서 다시 재방문하는 경우는 가능은 하지만 최소 거울을 써야 한다는 조건에 의해 정답이 될 수가 없음

⇒ 그렇다면 BFS 를 쓰는 편이 시간적으로 유리함

2️⃣ BFS를 쓰되 우선순위 큐를 섞어 쓰자

우선순위 큐를 쓴다면 최소 거울이라는 조건을 만족시킬 수 있을 것이라고 생각

🪴 풀이 🪴

👩🏻‍💻 코드

import sys
import heapq

N = int(sys.stdin.readline())
room = [list(sys.stdin.readline().rstrip()) for _ in range(N)]
v = [[[N*N for _ in range(4)] for _ in range(N)] for _ in range(N)]

dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]

def canGo(newX, newY):
  global room, v
  if newX < 0 or newX >= N or newY < 0 or newY >= N or room[newX][newY] == "*":
    return False
  else:
    return True

q = []

start = [-1, -1]
flag = False
for i in range(N):
  for j in range(N):
    if room[i][j] == "#":
      start = [i, j]
      flag = True
      for k in range(4):
        newX, newY = i + dx[k], j + dy[k]
        if canGo(newX, newY):
          heapq.heappush(q, ([0, newX, newY, k]))
          v[i][j][k] = 0
      break
  if flag:
    break

while q:
  mirror, x, y, d = heapq.heappop(q)

  if room[x][y] == "#":
    if x != start[0] or y != start[1]:
      print(mirror)
      exit(0)
    else:
      continue
  
  if room[x][y] == ".":
    newX, newY = x + dx[d], y + dy[d]
    if canGo(newX, newY) and mirror < v[newX][newY][d]:
      heapq.heappush(q, [mirror, newX, newY, d])
      v[newX][newY][d] = mirror

  elif room[x][y] == "!":
    newX, newY = x + dx[d], y + dy[d]
    if canGo(newX, newY) and mirror < v[newX][newY][d]:
      heapq.heappush(q, [mirror, newX, newY, d])
      v[newX][newY][d] = mirror 

    newD = (d - 1) % 4 # 오른쪽
    newX, newY = x + dx[newD], y + dy[newD]
    if canGo(newX, newY) and mirror+1 < v[newX][newY][newD]:
      heapq.heappush(q, [mirror+1, newX, newY, newD])
      v[newX][newY][newD] = mirror+1

    newD = (d + 1) % 4 # 왼쪽
    newX, newY = x + dx[newD], y + dy[newD]
    if canGo(newX, newY) and mirror+1 < v[newX][newY][newD]:
      heapq.heappush(q, [mirror+1, newX, newY, newD])
      v[newX][newY][newD] = mirror+1

print(result)

1️⃣ 변수 선언

• N: 집 크기
• room: 집 구성
• v: x좌표, y좌표, 해당 좌표에서 나가는 방향(0~3)을 의미하는 삼차원 배열
  이 좌표에서, 이 방향으로, 몇개의 거울을 써서 나갔는지를 의미함.
  초기값은 N*N(정확하게는 전체를 다 거울로 채워도 2개는 입구와 출구일테니 N*N-2 가 거울의 최댓값이므로 N*N-1 이 맞지만 편의상 저렇게 씀)
• dx, dy: 방향(0~3)에 따른 x축, y축 변화량

방향의 경우 오른쪽(0)을 시작으로 시계방향

2️⃣ 입구 좌표에서 상,하,좌,우로 나가는 경우를 큐에 삽입

• start: 입구 좌표가 담길 리스트
• flag: ‘#’ 이 집 구성에 두개 있으므로 ‘#’을 찾았는지 여부
• 4방향으로 갈 수 있는지 여부 확인 후, 우선순위 큐에 삽입하고 v를 갱신
• 큐에 삽입하는 값은 [거울수, x좌표, y좌표, 방향]

3️⃣ q 가 빌 때까지 반복

• 만약 도착하면, 우선순위 큐를 사용했으므로 가장 적은 수의 거울을 사용한 케이스. 따라서 거울 수를 출력 후 종료
• 좌표가 . 이라면
  • 직진
• 좌표가 ! 이라면
  • 직진
  • 90도 회전
  • -90도 회전
• 큐에 추가할 때는 해당 좌표를, 해당 방향으로 방문했을 때 사용하는 거울 수가 v 에 저장된 값보다 작다면 추가하고, 아니라면 추가하지 않음. 어차피 같은 방향으로 더 간단하게 갈 수 있는 방법이 있는데 굳이 더 많은 거울을 소모할 이유가 없음

4️⃣ canGo 함수

• 집 크기를 벗어나는 좌표는 아닌지, 벽으로 막힌 곳은 아닌지 확인함

---

🌻 후기 🌻

🤔 생각해볼 점

• DFS, BFS 를 적절한 순간에 잘 쓸 줄 알아야 함. 이런 식이면 곤란해~

🏛️삽질기

• DFS 로 어떻게든 풀어보려 했으나.. 시간 초과
• BFS 로도 약간 삽질하긴 했다(갱신된 방향을 v 처리했어야 했는데 그냥 기존 방향을 v처리하고 있었음) 능지 이슈