[백준 2151] 거울설치 (파이썬)

문제

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

문제유형

BFS, 구현

문제풀이

1. 처음 시작점에서 BFS방식으로 모든 방향으로 탐색한다. 탐색하면서 !를 만나면 90° 방향으로 방향을 바꿔 큐에 추가한다.
2. 제일 처음 종료지점에 다다르면 그때까지 사용한 거울개수 출력
   • BFS 특징은 가장먼저 접근한 순서가 최단거리이다. 즉 나중에 방문한 경로가 절대 최단거리가 될 수 없다.
   • 2번 조건이 성립하기 위해선 제일 먼저 종료지점에 다다른 경우가 가장 최소의 거울개수여야 하는데 BFS는 이 조건을 만족시킨다. 이 말은 거울을 한번 사용한 경우가 두번 사용한 경우보다 절대 뒤에 나올 수 없다.

고민했던 내용

주어진 맵과 동일한 형태의 visited 배열을 만들어서 방문한 거리를 저장했다. 방문한 거리를 접근할 때, 거리를 비교해서 항상 최단거리만 접근 할 수 있도록 제한했는데 여기서 오류가 발생해 한참 고민했다.

• 하지만 이 문제에서 최단거리가 최소 거울개수임을 보장하지 않는다. 따라서 위와 같은 접근방법은 잘못됐다.

<반례>

".!*......",
"..!.!*!.!",
"#.!*.*.*.",
"!!.*!.!*.",
".*.......",
".#......!",
".........",
".........",
"!.......!"

코드

1~18Line : input처리 및 #위치 검색해서 시작지점과 종료지점 좌표 저장
19~25Line : deque()를 통해 큐 생성해서 시작점에서 4방향으로 탐색하기위해 큐에 삽입. (0:오른쪽방향 1:아래방향 2:왼쪽방향 3:위쪽방향)
26Line~ : 큐에서 좌표와 방향정보 꺼내와서 꺼내온 방향으로 탐색시작. 탐색중 !를 만나면 방향을 바꿔서 큐에 삽입

# 백준 거울설치 2151번 골드4
from collections import deque

N = int(input())

listMap = []
listPos = []
visited = [[1000] * N for _ in range(N)]
dx = [0,1,0,-1]
dy = [1,0,-1,0]

for _ in range(N):
    listMap.append(list(map(lambda x:x, input())))

for i in range(N):
    for j in range(N):
        if listMap[i][j] == '#':
            listPos.append((i,j))

startPosX, startPosY, endPosX, endPosY = listPos[0][0], listPos[0][1], listPos[1][0], listPos[1][1]
q = deque()
q.append((listPos[0], 0, 0))
q.append((listPos[0], 0, 1))
q.append((listPos[0], 0, 2))
q.append((listPos[0], 0, 3))

while q:
    (posX, posY), mirrorCount, direction = q.popleft()
    
    movePosX = posX+dx[direction]
    movePosY = posY+dy[direction]
        
    while 0 <= movePosX < N and 0<= movePosY < N and listMap[movePosX][movePosY] != '*':
        if listMap[movePosX][movePosY] == "!":
            if direction == 0 or direction == 2:
                q.append(((movePosX,movePosY), mirrorCount+1, 1))
                q.append(((movePosX,movePosY), mirrorCount+1, 3))
            else:
                q.append(((movePosX,movePosY), mirrorCount+1, 0))
                q.append(((movePosX,movePosY), mirrorCount+1, 2))

        if movePosX == endPosX and movePosY == endPosY:
            q.clear()
            break

        movePosX += dx[direction]
        movePosY += dy[direction]        

print(mirrorCount)