문제:
- 제목: 숨바꼭질 3
- 링크 : https://www.acmicpc.net/problem/13549
- 접근 방법 : BFS ( + 0,1 가중치)
해결 방식:
Try 1 : Fail
- Max값 오판
- (최대 값으로 설정하자.. 100001) ```python import sys
sys.stdin = open(‘sample.txt’)
input = sys.stdin.readline
N,K = map(int, input().split()) visited = [0] * (100001) dw = [‘-1’,’1’, ‘Jump’]
from collections import deque
def bfs(): queue = deque() queue.append(N) visited[N] = 0 while queue: cur = queue.popleft() #print(cur, visited[cur]) if cur == K: print(visited[cur]) exit()
for step in dw:
if step != 'Jump':
update_time = 1
next = cur + int(step)
if next < 0 or next >= 100001 :
continue
if visited[next] !=0:
continue
visited[next] = visited[cur] + update_time
queue.append(next)
else:
update_time = 0
next = cur * 2
if next < 0 or next >= 100001:
continue
if visited[next] != 0:
continue
visited[next] = visited[cur] + update_time
queue.append(next) bfs() ``` ## Try 2 : Fail - 우선순위 적용 오판 - (순간이동은 value가 0 이고, 이동은 value가 1이라면, 최소 값을 구하는 문제에서는 value가 0이 queue의 앞으로 오도록해야한다.) - deque 에서는 appendleft를 하게되면 가장 앞으로 추가가 가능하다. ```python import sys
sys.stdin = open(‘sample.txt’)
input = sys.stdin.readline
N,K = map(int, input().split()) visited = [0] * (100001) dw = [‘-1’,’1’, ‘Jump’]
from collections import deque
def bfs(): queue = deque() queue.append(N) visited[N] = 0 while queue: cur = queue.popleft() #print(cur, visited[cur]) if cur == K: print(visited[cur]) exit()
for step in dw:
if step != 'Jump':
update_time = 1
next = cur + int(step)
if next < 0 or next >= 100001 :
continue
if visited[next] !=0:
continue
visited[next] = visited[cur] + update_time
queue.append(next)
else:
update_time = 0
next = cur * 2
if next < 0 or next >= 100001:
continue
if visited[next] != 0:
continue
visited[next] = visited[cur] + update_time
queue.appendleft(next) bfs() ``` ## Try3: 시간초과 - 문제 해결 방식의 로직에 문제가 있음을 깨달음 - 참조 코드 - [https://velog.io/@aonee/%EB%B0%B1%EC%A4%80-boj-13549-%EC%88%A8%EB%B0%94%EA%BC%AD%EC%A7%883-%ED%8C%8C%EC%9D%B4%EC%8D%AC](https://velog.io/@mang0206/%EB%B0%B1%EC%A4%80-13549-%EC%88%A8%EB%B0%94%EA%BC%AD%EC%A7%88-3-python) - heapq를 통해서 데이터를 처리한다. (아마 가중치가 다르니 해당 heapq를 통해서 가장 앞으로 오도록하는 것 같다.) - 근데 0 100000 의 testcase 값이 다르다.. - 어디가 문제 였는가?\ - 참고 코드 : https://aia1235.tistory.com/13 - 우선순위가 높은 JUMP 부터 값을 나타내줘야한다. (그렇지 않으면 다음 에러가 발생한다.) ```text 3
2 4 6
1 (3) (4) / (3) 5 8 / (5) 7 12 //괄호는 이미 방문해서 방문 안 함.
위와 같이 방문하면 걸린 시간은 +1 +1 이므로 2를 출력한다.
다른 방법으로 탐색을 X * 2, X - 1, X + 1 순으로 하면
3
6 2 4
12 5 7 / 8 (3) (5) / (4) 1 (3)
위와 같이 방문하면 순간이동은 0초 이므로 1을 출력한다.
즉, 우선ㅁ순위가 높은 것을 가장 앞으로 보내는 것 이외에, 가장 먼저 더이터를 처리할 필요가 있었다. (비용 처리때는 명심하기)
# 최종 코드
```python
import sys
sys.stdin = open('sample.txt')
input = sys.stdin.readline
N,K = map(int, input().split())
visited = [0] * (100001)
#dw = ['-1','1', 'Jump']
dw = ['Jump','-1','1']
from collections import deque
def bfs():
queue = deque()
queue.append(N)
visited[N] = 1
while queue:
cur = queue.popleft()
#print(cur, visited[cur])
if cur == K:
print(visited[cur]-1)
for step in dw:
if step != 'Jump':
update_time = 1
next = cur + int(step)
if next < 0 or next >= 100001 :
continue
if visited[next] !=0:
continue
visited[next] = visited[cur] + update_time
queue.append(next)
else:
next = cur * 2
if next < 0 or next >= 100001:
continue
if visited[next] != 0:
continue
visited[next] = visited[cur]
queue.appendleft(next)
bfs()
print()