문제
[실버1]
https://www.acmicpc.net/problem/1697
해설 없이 스스로 풀었나요?
△, 코드는 스스로 짜고 테스트 케이스 검색함 .. !
재풀이필요
아이디어
문제에서 "가장 빠른 시간"이라는 부분을 보고 BFS로 구현해야겠다고 생각했다.
주어진 N과 K의 범위까지의 배열을 만든다. 이 배열은 방문여부 및 거리(시간) 기록에 쓰인다.
문제를 통해 범위는 0 이상, 100001 이하로 설정하였다.
현재 지점에서 좌로 이동, 우로 이동 혹은 순간이동 했을 때 범위 내에 위치하고, 방문하지 않아 배열 값이 0이라면 Queue에 append하고 거리(시간)을 기록한다.
Queue를 도는 와중에 현재 위치가 목표 위치와 같다면 반복을 종료하고 배열에서 목표위치를 인덱스로 하는 값을 출력한다.
풀이
from collections import deque
def bfs(start):
q = deque([start])
time[start] = 0
while q:
now = q.popleft()
# print(q)
if now == k:
return
dx = [-1, 1, now]
for i in dx: # 좌우이동 혹은 순간이동
# print(now + i)
if now + i >= 100001 or now + i < 0: # 범위를 어어나면
continue
if time[now+i] == 0: # 방문하지 않았다면
q.append(now+i)
time[now+i] = time[now] + 1
n, k = map(int, input().split())
time = [0 for _ in range(100002)]
bfs(n)
print(time[k])Comment
처음에 문제에서 n과 k가 100,000까지였으므로 범위를 200,001까지로 설정해야 된다고 생각하였는데 애초에 이동할 수 있는 가짓수 중 나누기는 없으므로 200,000까지 가서 -1로 움직일 일이 없었다. 만약 세가지 움직임 중 하나를 했을 때 100,001을 넘는다면 그 이동은 하지 말아야 한다.
따라서 범위는 0이상, 100,001 이하로 설정하는 것이 맞다.
테스트케이스의 경우 답이 맞는데, 틀렸다고 채점되길래 테스트케이스를 검색해 실행해보았다.
100 0 # 100
6 16 # 3
8 20 # 3
15964 89498 # 4781
3 43 # 6
4 27 # 5
5 35 # 5
6 43 # 5
7 43 # 6
100 1 # 99
10 19 # 2
5 19 # 3
1 20 # 5
100000 100000 # 0
0 100000 # 22
100000 0 # 100000
0 1 # 1
3482 45592 # 637
2 4 # 1
9 5 # 4
5 5 # 0
5 17 # 4이 중 걸렸던 부분은 <0 100000 # 22> 과 <5 5 # 0> 였다.
0 100000 # 22 의 경우 while문을 돌며 이동할 때 범위를 벗어났는지 확인하지 않아서였다. 처음에는 이 문제에서 범위설정을 어떻게 해야하나, (보통 다른 문제에서는 그래프의 가로 세로 길이를 벗어나면 으로 설정하기 때문에) 무제한으로 늘어날 수 있지 않나 생각했는데 순간이동(좌표 2배이동)은 가능하지만 목표지점보다 말도 안되게 커졌을 경우 탐색할 이유가 없어 탐색범위를 설정해주어야 했다.
그렇게 첫번째 테스트케이스에 대해 해결하였다.
5 5 # 0 의 경우 처음에 시작위치에서 -1, 1 2을 먼저 queue에 append하고 방문했음을 표시한 후 while문을 돌도록 코드를 짜서 시작위치와 도착위치가 같은 경우에도 탐색을 진행하여 0이 아닌 다른 값이 출력되었다.
이를 해결하기 위해 n과 k가 같은 경우 BFS를 수행하지 않고 바로 0을 출력할 수 있도록 했고, 추후 코드를 완전히 수정하여 시작위치에서 바로 BFS 함수를 호출하도록 하였다.
처음에 -1, 1 2를 먼저 queue에 넣은 이유는 .. 토마토 문제에서 겪은 것 때문인걸까 어차피 bfs함수에서 다 진행되는 내용인데 .. 이럴 필요가 없다.
# from collections import deque
# def bfs():
# while q:
# now = q.popleft()
# # print(q)
# if now == k:
# return
# dx = [-1, 1, now]
# for i in dx: # 좌우이동 혹은 순간이동
# # print(now + i)
# if now + i >= 200000 or now + i < 0: # 범위를 어어나면
# continue
# if time[now+i] == 0: # 방문하지 않았다면
# q.append(now+i)
# time[now+i] = time[now] + 1
# else:
# if time[now+i] >= time[now] + 1:
# q.append(now+i)
# time[now+i] = time[now] + 1
# n, k = map(int, input().split())
# time = [0 for _ in range(200001)]
# q = deque()
# q.append(n-1)
# q.append(n+1)
# q.append(n*2)
# time[n-1] = 1
# time[n+1] = 1
# time[n*2] = 1
# if n == k:
# print(0)
# else:
# bfs()
# print(time[k])
# # print(time)
마지막 의문은 "방문하지 않았을 경우(배열 값이 0인 경우)"에만 탐색을 진행해도 되는가 였다.
아래는 내가 제출한, 정답이 된 코드이다.
from collections import deque
def bfs(start):
q = deque([start])
time[start] = 0
while q:
now = q.popleft()
# print(q)
if now == k:
return
dx = [-1, 1, now]
for i in dx: # 좌우이동 혹은 순간이동
# print(now + i)
if now + i >= 100001 or now + i < 0: # 범위를 벗어나면
continue
if time[now+i] == 0: # 방문하지 않았다면
q.append(now+i)
time[now+i] = time[now] + 1
else:
if time[now+i] >= time[now] + 1:
q.append(now+i)
time[now+i] = time[now] + 1
n, k = map(int, input().split())
time = [0 for _ in range(100002)]
bfs(n)
print(time[k])보다시피 나는 범위를 벗어나면 continue, 범위 내에 위치하고 방문하지 않았다면 큐에 삽입하고 다음 탐색할 위치에 대해 거리 값을 현재 위치 + 1로 업데이트 해주었다.
그리고 else 구문을 보면, 이미 방문을 했고, 다음 탐색할 위치에 있는 거리값이 현재 위치 + 1 보다 크다면 더 작은 거리로 갱신할 수 있으므로 큐에 삽입하고 거리 값을 현재 위치 + 1로 갱신할 수 있도록 구현했다.
그러나 구글링했을 때 else 구문을 제외하고 범위 내에 위치하고 방문하지 않았을 경우에 대해서만 탐색을 진행하는 코드가 많고 모두 정답이었다.
실제로 프린트를 찍어보니 else문을 도는 경우는 모두 이미 방문했을 때 기록된 거리값이 현재 방문하여 갱신하려는 값보다 작았다.
https://ji-gwang.tistory.com/298
위 게시글을 참고하면 조금 더 이해가 될 것 같다.
따라서 방문하지 않은 경우에 한해서 탐색을 수행해도 된다!
