6087번 문제
BFS 탐색문제이다.
처음에 거울 설치 횟수를 어떻게 셀까를 고민했을때 든 생각은 바로 전의 이동방향을 생각해서, 전의 이동방향과 다른 방향으로 갔을 때, 거울 설치 횟수를 늘렸다.
하지만 이렇게 했을 경우에 한가지 문제가 생겼다.
아래와 같은 예시가 있을때
4 5
C . . *
. . . *
. . . *
* . * *
. . . C
(0,0)인덱스의 지점에서 BFS 탐색을 시작하면 ↓, -> 두방향으로 탐색을 한다.
문제는 여기서 발생한다.
(1,0)에서 다시 탐색을 하면 ↓, -> 을 탐색하고, (1,1) 지점에 거울을 1번 설치했다고 방문처리한다.
그후에 (0,1)이 탐색을 해서 (1,1)을 방문하면, 기존에 방문을 했고, 거울 설치횟수도 동일하므로 그냥 지나치게 되는것이다.
하지만 결과는 (0,0)->(0,1)->(1,1) 순서로 탐색하는것이 정답이다.
여기서 유의미한 결과를 얻을 수 있다.
탐색중 다음 진행구역이 이미 방문해있다면, 거울설치 횟수가 이전의 거울설치 횟수보다 작거나 같으면 큐에 넣는것이다.
그럼 위의 내용을 가지고 어떻게 구현을 해야 재방문에 대한 문제를 해결할 수 있을까?
처음엔 BFS 탐색 코드에 visited[x][y]==0 일때랑 visited[x][y]!=0 일때를 나눠서 구현을 하고,
visited[x][y]!=0일때. 즉, 재방문할때 거울설치 횟수가 이전의 거울설치 횟수보다 작거나 같으면 큐에 넣는것을 구현했었다.
하지만, 이렇게 하면 무한루프에 빠지게 된다.
따라서 생각해낸 방법이 한쪽씩 탐색을 다 마치고 다음 방향을 탐색하는 것이다.
즉, 탐색 시작점에서 위를 먼저 탐색한다고 하면, 윗방향으로 모든 탐색을 마치고, 다음방향을 탐색하는 것이다.
이를 바탕으로 코드를 짜보면
import sys
from collections import deque
def bfs(x,y):
q=deque()
q.append([x,y])
visited[x][y]=0
while q:
x,y=q.popleft()
if (x,y)==(end_x,end_y):
return visited[x][y]-1
for i in range(4):
d=1 #한쪽 방향을 먼저 탐색하기 위한 변수
while True: #한쪽을 탐색하기 위한 while문
#dx,dy에는 1혹은 -1만 들어가기 때문에 *d를 해줘서 일렬로 탐색할 수 있도록 한다.
nx=x+dx[i]*d
ny=y+dy[i]*d
# 배열안에 있을 때
if not(0<=nx<h and 0<=ny<w):
break
# 벽이 아닐때
if graph[nx][ny]=="*":
break
# 이미 방문 했다면, 현재값+1 이 이미 방문한 값보다 크다면
if visited[nx][ny]<visited[x][y]+1 and visited[nx][ny]!= -1:
break
#위의 세 조건을 통과하면
q.append([nx,ny])
visited[nx][ny]=visited[x][y]+1
d+=1
input=sys.stdin.readline
w,h=map(int, input().split())
graph=[]
for _ in range(h):
graph.append(list(map(str, input().rstrip())))
dx=[-1,1,0,0]
dy=[0,0,-1,1]
visited=[[-1 for _ in range(w)]for _ in range(h)]
c_lst=[]
for i in range(h):
for j in range(w):
if graph[i][j]=="C":
c_lst.append([i,j])
start_x,start_y=c_lst[0][0],c_lst[0][1]
end_x,end_y=c_lst[1][0],c_lst[1][1]
print(bfs(start_x,start_y))쉽다고 느꼈지만, 한쪽방향 탐색과 재방문에 대한 처리때문에 애를 먹은 문제였다.
