https://www.acmicpc.net/problem/6087
6087번: 레이저 통신크기가 1×1인 정사각형으로 나누어진 W×H 크기의 지도가 있다. 지도의 각 칸은 빈 칸이거나 벽이며, 두 칸은 ‘C’로 표시되어 있는 칸이다. ‘C’로 표시되어 있는 두 칸을 레이저로 통신하기 위해서www.acmicpc.net
처음엔, 모든 방향으로 더이상갈수없을때까지 bfs를 반복하다보면 답이 나올거라 생각했다.
근데 50%정도에서 계속 틀려서 반례를보니깐
4 4C……....C
다음과같은반례가 있었다.
요점은, 한 지점에 도착하는 최소경로가, 방향에 따라 최적의 정답이 아닐 수 있다는 것이다.
따라서, 만일 bfs를 진행하다가, 다음 방문점이 지금의 방문점보다 클때만 탐색을 진행하고, 만일 크다면 덮어쓰는것이다.
코드보면뭔소린지알거다
백준 정답자들중에선 잘 푼듯 하다.
import sysfrom collections import dequeinput=sys.stdin.readline
move=[[-1,0],[1,0],[0,-1],[0,1]]def bfs(): que=deque([start])
arr[start[0]][start[1]]=-1 while que: cx, cy=que.popleft()
for a,b in move: nx,ny=cx+a,cy+b
while 0<=nx<h and 0<=ny<w and arr[nx][ny]!='*':
if (arr[nx][ny] in('.','C'))or arr[cx][cy]<arr[nx][ny]:
#더이상 한 방향으로 나아갈때가 없을때까지
if arr[nx][ny]=='C':
print(arr[cx][cy]+1) exit()
arr[nx][ny]=arr[cx][cy]+1
que.append([nx,ny]) nx+=a
ny+=b else: break
w,h=map(int,input().split())C=[]arr=[]
for i in range(h): tmp=list(input().rstrip()) arr.append(tmp)
for j in range(w): if tmp[j]=='C': C.append((i,j))
start,end=Cbfs()print(arr)