티스토리 뷰
반응형
문제: www.acmicpc.net/problem/13913
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
|
import sys
from collections import deque
N,M = map(int,input().split())
loc=[sys.maxsize]*100001
loc[N]=0
li=[]
def bfs(n):
q=deque()
cnt=0
q.append([n,cnt])
while q:
a=q.popleft()
if a[0]==M:
print(a[1])
li.append(a[0])
while loc[li[-1]]!=0:
if li[-1]-1>=0 and loc[li[-1]]-1==loc[li[-1]-1]:
li.append(li[-1]-1)
elif li[-1]+1<100000 and loc[li[-1]]-1==loc[li[-1]+1]:
li.append(li[-1]+1)
elif li[-1]%2==0 and loc[li[-1]]-1==loc[li[-1]//2]:
li.append(li[-1]//2)
li.reverse()
print(' '.join(map(str,li)))
break
if a[0]-1>=0:
if a[1]+1<loc[a[0]-1]:
loc[a[0]-1]=a[1]+1
q.append([a[0]-1,a[1]+1])
if a[0]*2<=100000 and M*2>a[0]*2:
if a[1]+1<loc[a[0]*2]:
loc[a[0]*2]=a[1]+1
q.append([a[0]*2,a[1]+1])
if a[0]+1<=100000:
if a[1]+1<loc[a[0]+1]:
loc[a[0]+1]=a[1]+1
q.append([a[0]+1,a[1]+1])
bfs(N)
|
cs |
위의 코드는 시간초과가 난 코드다.
시간초과가 난 이유는 해당 값을 찾고나서 역 추적하여 찾는 과정에서 시간초과가 난 것 같다.
고민을 해봤지만 도저히 생각이 나질 않아서 다른 분의 코드를 참고했다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
|
import sys
from collections import deque
def solve(visited,n,k):
queue=deque()
queue.append(n)
while queue:
x=queue.popleft()
if x==k:
#이동하는데 걸리는 최소시간
print(visited[x])
#이동한방법은 이동경로를 역순으로 출력
p=[]
#p에다가 마지막경로인 x를 넣고
#x에다가 다시 path에 저장해둔 이전의 좌표 넣기
#x가 시작점과 같아질때까지 반복
while x!=n:
p.append(x)
x=path[x]
#while문이 n일때 나가니깐 n은 추가해주기
p.append(n)
p.reverse()
print(' '.join(map(str,p)))
return
for nx in (x+1,x-1,x*2):
if 0<=nx<100001 and visited[nx]==0:
visited[nx]=visited[x]+1
#path[다음좌표]=현재좌표
path[nx]=x
queue.append(nx)
n,k=map(int,input().split())
visited=[0]*100001
path=[0]*100001
solve(visited,n,k)
|
cs |
풀이 접근법은 visited와 path를 둔 다음에 visited는 최소시간을 계산하는 데 이용하고 path는 경로를 찾는데 이용한다.
이때 path는 이전 방문위치를 저장한다. 그러면 이제 계속 역추적하다 보면 n까지 도달한다. 하지만 위의 코드에서 while은 n이 아닐때까지 이므로 그 다음줄에 n을 추가해준다. 그리고 뒤에서 앞으로 저장되어 있으므로 reverse를 이용하여 정렬하면 답을 찾을 수 있다.
반응형
'알고리즘 > 백준' 카테고리의 다른 글
1261번 알고스팟 백준 파이썬 (0) | 2020.12.15 |
---|---|
14226번 이모티콘 백준 파이썬 (0) | 2020.12.15 |
13549번 숨바꼭질3 백준 파이썬 (0) | 2020.12.14 |
1697번 숨바꼭질 백준 파이썬 (0) | 2020.12.14 |
2146번 다리 만들기 백준 파이썬 (0) | 2020.12.13 |
반응형
공지사항
최근에 올라온 글
최근에 달린 댓글
- Total
- Today
- Yesterday
링크
TAG
- Spring
- thread
- setattr
- docker-compose
- Command Line
- 카카오
- 프로그래머스
- 자바
- ubuntu
- 파이썬
- postgres
- Python
- docker
- env
- Collections
- 백준
- Pattern
- dockerignore
- headers
- 그래프
- Java
- Linux
- 2021 KAKAO BLIND RECRUITMENT
- django
- 알고리즘
- Celery
- DRF
- 면접
- BFS
- PostgreSQL
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | 7 |
8 | 9 | 10 | 11 | 12 | 13 | 14 |
15 | 16 | 17 | 18 | 19 | 20 | 21 |
22 | 23 | 24 | 25 | 26 | 27 | 28 |
29 | 30 | 31 |
글 보관함