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

2151번: 거울 설치

하.. 이 문제는 일주일 동안 나를 괴롭혔기에 더욱 각별하다.. 정말 많이 고민 했는데 답 보기가 너무 자존심 상해서 끝까지 답을 안 보고 혼자 고민했다. 길을 걸을 때나 샤워할 때나 자기 전에나 계속 머릿 속으로 문제 푸는 그런 거.. 다들 경험 있으리라 생각한다. 이틀에 한 번 정도 풀어서 제출하고 틀리고를 반복하다 오늘 뭔가 다시 풀어보자! 해서 풀었는데 역시나 제출하자마자 "틀렸습니다"를 받았다. 질문 게시판에 있는 반례를 모두 넣어보며 내 코드의 오류를 찾았고, 결국 'pass'를 받아냈다. 그리고 시간 3등도 달성했다 ㅋㅋㅋㅋ

거창하게 말했지만 코드를 보면 생각보다 간단하다. 핵심은, 모든 경우를 빠짐없이 고려하는 것이다.

• 사용 알고리즘 : BFS 최단 경로 알고리즘
• 도착 좌표를 만났다고 바로 리턴해버리는 것이 아니라 이후에 또 갱신될 수 있기 때문에 큐에 값이 있는 동안 끝까지 다 해봐야한다!!!!!(내가 놓친 많은 부분들 중 하나이다)
• Input 받으면서 시작좌표(sr, sc), 도착좌표(gr, gc)를 저장한다.
• 혼자 착각한 것은 맵의 테두리가 벽("*")에 둘러쌓여 있다고 생각한 것이다. 문제에 그런 말이 없기 때문에 맵 내이고, 벽이 아니라면 모두 탐색해야 하므로 큐에 좌표와 방향을 모두 담아준다!!!! 멍청하게 처음에 맵의 안쪽을 가리키는 한 방향만 넣어줬다.. 내 마음대로 문제를 해석하지 말자
• BFS 함수 내에서 check를 맵의 크기대로 그리되, 각 위치별로 4방향(상하좌우) 정보를 담을 수 있도록 * 4 해줬다.
• 거울 사용 횟수를 표현할 것이므로 check배열의 초기화는 -1로 해줬다.
• 최초의 큐에 담긴 위치와 방향 값을 돌리며 check 배열에 0으로 표시한다. 거울을 아직 사용하지 않은 경우이므로 0이다.
• 큐에서 값을 하나씩 꺼내며 너비우선탐색으로 갈 수 있는 곳을 퍼트린다.
• 이동할 곳이 격자 밖이거나 벽이면 continue
• 그리고 크게 두 가지 경우로 빈 공간("*") 이거나 거울을 설치할 수 있는 곳("!") 일 때로 나누어 조건문을 구성했다.
  • 그리고 두 경우에 대해 첫 방문인 경우, 그리고 이미 방문한 적이 있는 경우일 때로 또 두 경우를 나누었다.
    • 첫 방문인 경우는 그대로 이동할 곳을 거울 사용 횟수로 표시하고, 큐에 값을 담았다.
    • 이미 방문한 적이 있는 경우에는 최솟값으로 갱신할 수 있는 경우에만 거울 사용 횟수를 표시하고, 큐에 값을 담았다.
    • 추가로 고려한 것은 거울을 설치할 수 있는 곳에 거울을 설치하는 경우와 거울을 설치하지 않는 경우로 두 경우를 나누었다.
      • 거울 설치하지 않는 경우는 빈 공간에 가는 경우와 같이 첫 방문일 때, 이미 방문 표시가 되어 있는 경우를 각각 처리해준다.
      • 거울을 설치하는 경우, 미리 만들어둔 changeDir에서 현재 방향에서 갈 수 있는 두 가지 방향에 대해 새로운 방향을 검사하는데, 이 때도 마찬가지로 첫 방문일 때와, 이미 방문 표시가 되어 있을 때를 구분해 각각 처리해준다.
    • 이렇게 모든 경우에 대해 조건문을 구성해야 한다.
• 큐에 있는 모든 값의 검사가 끝나면!!! 다 퍼트린 것이다.
• 그 때, check 배열의 목적지(gr, gc)에 담긴 상하좌우에 해당하는 4개 값 중 -1을 제외하고 가장 적은 거울 사용횟수를 리턴한다.
• 성급하게 큐에서 뽑은 gr, gc일 때 값을 리턴해버리면 절대 안 된다.. 목적지에 첫 도착 이후에도 언제든 최솟값으로 갱신될 수 있기 때문이다..

 

내가 pass를 받는데 도움이 된 두 개의 반례이다.

Input:

8
***#****
*!.!..!*
*......*
*..*...*
*!!....*
*.!!..!*
*......*
***#****

Correct answer: 4

 

Input:
9
.!*......
..!.!*!.!
#.!*.*.*.
!!.*!.!*.
.*.......
.#......!
.........
.........
!.......!

Correct answer: 3

---

파이썬 코드는 다음과 같다.

---

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

# 상하좌우
dr = (-1, 1, 0, 0)
dc = (0, 0, -1, 1)
changeDir = ((2, 3), (2, 3), (0, 1), (0, 1))

def bfs():
    check = [[[-1] * 4 for _ in range(N)] for _ in range(N)]
    for sr, sc, sd in Q:
        check[sr][sc][sd] = 0
    while Q:
        r, c, d = Q.popleft()
        nr = r + dr[d]
        nc = c + dc[d]
        # 격자 밖이거나 벽이면
        if not (0 <= nr < N and 0 <= nc < N) or A[nr][nc] == "*":
            continue
            
        # 빈 공간인 경우
        if A[nr][nc] == ".":
            if check[nr][nc][d] == -1:      # 첫 방문
                check[nr][nc][d] = check[r][c][d]
                Q.append((nr, nc, d))
            else:     # 이미 방문했다면 갱신할 수 있는 경우에만
                if check[nr][nc][d] > check[r][c][d]:
                    check[nr][nc][d] = check[r][c][d]   # 최솟값 갱신
                    Q.append((nr, nc, d))
                    
        # 거울 설치할 수 있는 경우
        elif A[nr][nc] == "!":
            # 거울 설치 X
            if check[nr][nc][d] == -1:      # 첫 방문
                check[nr][nc][d] = check[r][c][d]
                Q.append((nr, nc, d))
            else:     # 이미 방문했다면 갱신할 수 있는 경우에만
                if check[nr][nc][d] > check[r][c][d]:
                    check[nr][nc][d] = check[r][c][d]   # 최솟값 갱신
                    Q.append((nr, nc, d))
            # 거울 설치 O
            for nd in changeDir[d]:
                if check[nr][nc][nd] == -1:     # 첫 방문
                    check[nr][nc][nd] = check[r][c][d] + 1
                    Q.append((nr, nc, nd))
                else:     # 이미 방문했다면 갱신할 수 있는 경우에만
                    if check[nr][nc][nd] > check[r][c][d] + 1:      # 최솟값 갱신
                        check[nr][nc][nd] = check[r][c][d] + 1
                        Q.append((nr, nc, nd))

    temp = []   # 가능한 경우의 수
    for chk in check[gr][gc]:
        if chk == -1:
            continue
        temp.append(chk)
    return min(temp)

# main
N = int(input())
A = []
doors = []
for i in range(N):
    A.append(list(input().strip()))
    for j in range(N):
        if A[i][j] == "#":
            doors.append([i, j])
            A[i][j] = "."

sr, sc = doors[0]   # 시작 좌표
gr, gc = doors[1]   # 도착 좌표

Q = deque()
for d in range(4):
    nr = sr + dr[d]
    nc = sc + dc[d]
    if not (0 <= nr < N and 0 <= nc < N) or A[nr][nc] == "*":
        continue
    Q.append((sr, sc, d))   # 시작 가능한 방향 모두 큐에 담기

print(bfs())

---

• 시간 : 160ms / 메모리 : 125264kb
• 고찰 : 배운 점이 많은 좋은 문제였다. 최근에 백준의 아래 첨부한 로봇 문제를 풀어본 것이 많은 도움이 되었다. 문제를 내 마음대로 해석하지 말자. 그리고 모든 가능한 경우의 수에 대해 꼼꼼하게 고려해 예외케이스에 걸리지 않도록 하자. 남들에겐 쉬운 문제일진 몰라도 내겐 뭔가 오래 기억될 문제 같다..ㅋㅋㅋㅋ 계속 틀려서 찝찝했는데 pass 한 방에 해소됐다. 연습만이 살 길이다.

[BOJ] 1726. 로봇(Python) / BFS