[DFS/BFS/완전탐색] ★★ 2151번 - 거울 설치(BFS)

[백준] 2151번 - 거울 설치

풀이 시간: 3시간 이내

유사 문제: 2206

https://hseungyeon.tistory.com/223

[DFS/BFS/완전탐색] ★★ 2206번 - 벽 부수고 이동하기(BFS)

 

1) 문제 해결 아이디어

문제를 읽었는데 문제 이해가 가질 않아서 15분정도 고민하다가 검색을 했고 도움을 받았다.

문제 자체가 이해가 가지 않아 어려움을 겪은 문제였다. 문제를 다 이해하고나서도 여러가지 오류를 해결하는데 시간이 오래걸렸기 때문에 추후 복습이 꼭 필요한 문제!!

문제를 다이해

<문제 이해하기>

1. 거울을 설치할 때에는 45도 기울어진 대각선 방향으로 설치해야 한다.

거울을 대각선으로 설치하는 것은 직진하는 빛이 거울에 의해 90도로 꺾인다는 의미이다.

즉, 90도로 꺾인 빛은 2가지 방향 중 1개로 나아간다.

2. 모든 거울은 양면 거울이기 때문에 양 쪽 모두에서 반사가 일어날 수 있다. 

어느 방향에서 빛이 들어오든 간에 90도로 꺾여 빛이 나아간다. 

즉, 2개중 어느 문으로 빛이 들어와도 상관없다. (시작점은 아무 문이나 상관 없음)

[참고] https://peisea0830.tistory.com/98

[Python 3] BOJ - 2151 "거울 설치"

 

<동작 과정>

1. 필요 변수들 생성

<주요 변수>

graph: 입력받은 정보(2차원 리스트)

visited: i행 j열 dir방향으로 올 때 필요한 거울 개수(3차원 리스트) → 가장 중요!!

(행과 열의 크기는 n, 방향은 4개이므로 n * n * 4 의 크기로 -1 초기화하여 생성한다.)

2. 문 위치 찾기: 시작점(start), end(목표점) 좌표 구하기

3. bfs(start, end) 호출

 

<bfs 동작 과정>

1. 시작점 4방향 삽입, 방문 처리

시작점은 아직 거울을 0개 사용하였으므로 0으로 초기화해야함

2. 큐에서 좌표, 방향(x, y, dir) popleft()

3. 범위 내이면

3-1. 빈칸(.)/목표점(#)이면 

  3-1-1. 방문한적 없으면 → 해당 좌표, 같은방향으로 삽입, 방문처리

  3-1-2. 방문한적 있고 더 적은 거울을 사용했다면 → 현재값으로 업데이트(해당 좌표, 같은방향으로 삽입, 방문처리)

3-2. 거울 설치가 가능한 위치(!)면

  3-2-1. 거울 설치X

    3-2-1-1. 방문한적 없으면 → 해당 좌표, 같은방향으로 삽입, 방문처리

    3-2-1-1. 방문한적 있고 더 적은 거울을 사용했다면 → 현재값으로 업데이트(해당 좌표, 같은방향으로 삽입, 방문처리)

  3-2-2. 거울 설치O

    3-2-2-1. 방문한적 없으면 → 해당 좌표, 90도 꺾은 2가지 방향으로 삽입, 방문처리

    3-2-2-1. 방문한적 있고 더 적은 거울을 사용했다면 → 현재값으로 업데이트(해당 좌표, 90도 꺾은 2가지 방향으로 삽입, 방문처리)

 

Q. (dir + 1) % 4, (dir + 3) % 4 에 대해 for문을 돌리는 이유는?

거울을 설치하면 방향(dir)은 90도 꺾인 2가지 방향으로 나아갈 수 있는데 그것을 수식화한게 (dir + 1) % 4, (dir + 3) % 4 이다. 여기서 0: 북, 1: 서, 2: 남, 3: 동 으로 설정했기 때문에 들어오는 방향(dir)은 아래와 같이 나아가게 된다. 

방향(dir)	90도 꺾여 나아가는 방향
0	1, 3
1	2, 0
2	3, 1
3	0, 2

 

첫번째 오류. 틀렸습니다

1. 더 적은 거울을 사용했는지 확인하는 조건을 잘못 코딩함

운좋게? 테스트 케이스에서는 문제가 없어서 올바른 답이 나왔지만 막상 제출을 하니 바로 틀렸습니다가 나왔다. 줄에 있는 조건을 반대로 (visited[nx][ny][dir] < visited[x][y][dir]) 으로 설정하여 문제가 되었다.

여기서 visited[nx][ny][dir]은 이전에 방문했던 적이 있는 곳으로 비교해야할 기준 대상이고

visited[x][y][dir]은 우리가 위에서 popleft()한 곳에 해당하는 값으로 x행 y열의 dir방향에 오기까지 사용된 거울의 개수이다. 

 

2. 다른 문(목표점)에 도달하면 바로 값을 리턴해버림

원래 줄에 popleft()한 좌표가 다른문(목표점)의 좌표와 같다면 아래 코드처럼 해당칸, 방향에 오기까지 거울 개수를 바로 리턴해버리고 그 값을 출력시켰다. 

# 다른문(목표점)에 도달하면 최소 거울 개수 리턴
if((x, y) == end):
  return visited[x][y][dir]

Q. 목표점에 도달했을 때 바로 값을 리턴하면 안되는 이유는?

일반적인 BFS 문제라면 최단 경로를 구하는 것이기 때문에 목표점에 도달했을 때 그 값을 바로 리턴한다고 해서 문제가 되지 않는다. 하지만 이 문제같은 경우엔 최단 경로가 아니라 목표점에 도달하기까지 사용해야하는 최소 거울 개수를 구하는 것이다. 방향을 신경쓰지 않고 단순히 목표점에 도착했을 때 값을 바로 리턴해버린다면 목표점의 좌표에서 다른 방향일 때의 값들을 고려하지 못하는 문제가 생긴다. 

예를 들어, 목표점이 (4, 1)일 때 방향은 4개로 visited[4][1][0], visited[4][1][1], visited[4][1][2], visited[4][1][3]이 있고 차례대로 4, 3, 2, 1이라고 해보자. 만약 제일 먼저 pop된 방향이 0이어서 바로 그 값(4)를 리턴해버린다면 실제로는 최소값(1)이 리턴되지 못하는 오류가 발생한다.

그러므로 해당좌표, 모든 방향에 대해서 -1이 아닌 값들 중 최소값을 구해야한다!!!!

 

[참고] https://chelseashin.tistory.com/81

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

 

2) 소스코드

from collections import deque
import sys
input = sys.stdin.readline

# BFS
def bfs(start, end):
  queue = deque()
  # 시작점 4방향으로 삽입, 방문처리
  for i in range(4):
    queue.append((start[0], start[1], i))
    visited[start[0]][start[1]][i] = 0 

  while queue:
    x, y, dir = queue.popleft()
    nx = x + dx[dir]
    ny = y + dy[dir]
    # 범위내이고
    if(0 <= nx < n and 0 <= ny < n):
      # 1. 빈 칸 혹은 다른문(목표점)이면
      if(graph[nx][ny] == '.' or graph[nx][ny] == '#'):    
        # 1-1. 방문한적 없으면 
        if(visited[nx][ny][dir] == -1): 
          queue.append((nx, ny, dir))  # 같은 방향
          visited[nx][ny][dir] = visited[x][y][dir]
        # 1-2. 방문한적 있고 더 적은 거울을 사용했다면 업데이트
        else: 
          if(visited[nx][ny][dir] > visited[x][y][dir]):          
            queue.append((nx, ny, dir))  # 같은 방향
            visited[nx][ny][dir] = visited[x][y][dir]
      # 2. 거울 설치가 가능한 위치면 
      elif(graph[nx][ny] == '!'):
        # 2-1. 거울 설치X 
        # 2-1-1. 방문한적 없으면
        if(visited[nx][ny][dir] == -1):
          # 같은 방향으로 삽입, 방문 처리
          queue.append((nx, ny, dir))  # 같은 방향
          visited[nx][ny][dir] = visited[x][y][dir]
        # 2-1-2. 방문한적 있고 더 적은 거울을 사용했다면
        else:
          if(visited[nx][ny][dir] > visited[x][y][dir]):
            # 더 적은 거울을 사용한 현재값으로 업데이트
            queue.append((nx, ny, dir))  # 같은 방향
            visited[nx][ny][dir] = visited[x][y][dir]
        # 2-2. 거울 설치O
        for ndir in [(dir + 1) % 4, (dir + 3) % 4]:
          # 2-2-1. 방문한적 없으면 
          if(visited[nx][ny][ndir] == -1):
            # 같은 방향으로 삽입, 방문처리
            queue.append((nx, ny, ndir))
            visited[nx][ny][ndir] = visited[x][y][dir] + 1           # 2-2-2. 방문한적 있고 더 적은 거울을 사용했다면 
          else:
            if(visited[nx][ny][ndir] > visited[x][y][dir] + 1):
              # 더 적은 거울을 사용한 현재값으로 업데이트
              queue.append((nx, ny, ndir))
              visited[nx][ny][ndir] = visited[x][y][dir] + 1
  min_cnt = 1e9  # 최소 거울 개수
  # 최소 거울 개수 찾기
  for cnt in visited[end[0]][end[1]]:
    if(cnt == -1):  continue
    elif(min_cnt > cnt):  min_cnt = cnt
  return min_cnt
  
n = int(input())  # 집 크기
# n * n (#: 문, *: 벽, !: 거울설치가능, .:빈곳 )
graph = [list(input().strip()) for _ in range(n)]
# i행 j열 dir방향으로 올 때 필요한 거울 개수
visited = [[[-1] * 4 for _ in range(n)] for _ in range(n)]
# 북, 서, 남, 동
dx = [-1, 0, 1, 0]
dy = [0, -1, 0, 1]
start = (0, 0)  # 시작점
end = (0, 0)    # 목표점
doorNum  = 0    # 문 개수

# 문 위치 찾기
for i in range(n):
  # 2개 다 찾았으면 종료
  if(doorNum == 2):  break
  for j in range(n):
    if(graph[i][j] == '#'):
      # 첫번째 문이면 시작점으로
      if(doorNum == 0):
        start = (i, j)
        doorNum += 1
      else:
        end = (i, j)
        doorNum += 1
        break
    
print(bfs(start, end))