[백준]2151 거울설치

1. 풀이

(1) 설치횟수의 최솟값을 구한다. 설치할때만 이동거리를 +1해주고, 그렇지 않은 노드간의 연결은 +0

(2) 즉 간선간의 가중치가 다르므로(1 or 0) bfs가 아닌 다익스트라를 이용한다.

(bfs로 탐색하면, 처음으로 다른문(#)을 찾은 경우가 거울의 최소설치가 아닌, 거울설치에 제약이 없을 때 최소이동 경로가 된다. 따라서 모든경우를 다 탐색한 후 그 중 최소설치횟수를 찾아야함.)

(3) 이 문제는 특히 이동방향 상의 제약(빛은 직진만함)이 있기 때문에 한 노드(r,c)에 총 4번까지 방문이 가능하다. 따라서 한 노드 nodeDist[r][c]에 4방향의 저장소를 만든다

즉 nodeDist[r][c][k] : r,c에 k방향일때의 최소 설치횟수

​

2. 소스코드

import heapq

dR=[0,1,-1,0]
dC=[1,0,0,-1]

N=int(input())
L=[]
for i in range(N):
    L.append(list(input()))

isFind=False
for i in range(N):
    for j in range(N):
        if L[i][j]=="#":
            startR=i
            startC=j
            isFind=True
            break
    if isFind:
        break

maxNum=9876543210
nodeDist=[[[maxNum,maxNum,maxNum,maxNum] for j in range(N)] for i in range(N)]

def dijstra():
    dij=[[0,startR,startC,4]]
    for k in range(4):
        nodeDist[startR][startC][k]=0
    heapq.heapify(dij)
    while(dij):
        nowCost,r,c,d=heapq.heappop(dij)


        # 종료 #이면?
        if [r,c]!=[startR,startC] and L[r][c]=="#":
            print(nowCost)
            break

        # 시작 #이면?
        if L[r][c]=="#":
            for k in range(4):
                tempR=r+dR[k]
                tempC=c+dC[k]
                if 0<=tempR<N and 0<=tempC<N and L[tempR][tempC]!="*":
                    nodeDist[tempR][tempC][k]=0
                    dij.append([0,tempR,tempC,k])
        # . 이면?
        elif L[r][c]==".":
            # 이미방문되었으면 종료
            if nodeDist[r][c][d]<nowCost:
                continue
            tempR=r+dR[d]
            tempC=c+dC[d]
            if 0<=tempR<N and 0<=tempC<N and L[tempR][tempC]!="*" and nowCost<nodeDist[tempR][tempC][d]:
                nodeDist[tempR][tempC][d]=nowCost
                heapq.heappush(dij,[nowCost,tempR,tempC,d])
        # !이면?
        else:
            if nodeDist[r][c][d]<nowCost:
                continue
            for k in range(4):
                if k+d==3:
                    continue
                # 거울설치 안하면?
                elif k==d:
                    tempR=r+dR[k]
                    tempC=c+dC[k]
                    if 0<=tempR<N and 0<=tempC<N and L[tempR][tempC]!="*" and nowCost<nodeDist[tempR][tempC][d]:
                        nodeDist[tempR][tempC][d]=nowCost
                        heapq.heappush(dij,[nodeDist[tempR][tempC][d],tempR,tempC,d])
                # 거울설치?
                else:
                    tempR=r+dR[k]
                    tempC=c+dC[k]
                    if 0<=tempR<N and 0<=tempC<N and L[tempR][tempC]!="*" and nowCost+1<nodeDist[tempR][tempC][k]:
                        nodeDist[tempR][tempC][k]=nowCost+1
                        heapq.heappush(dij,[nodeDist[tempR][tempC][k],tempR,tempC,k])




dijstra()
'''
for i in range(N):
    print(nodeDist[i])
'''