[백준13913] / 숨바꼭질 4 - BFS

2024. 10. 18. 17:56·Programming/Algorithm

 

백준13913

 

푼 날짜 : 2024.10.18

푼 문제 : [13913] / 숨바꼭질 4

사용한 언어 : python

알고리즘 : BFS

 

 

접근 방식 :

가장 빠른 시간을 출력하는 것은 사실 이전과 비슷한 문제이기 때문에 어렵지 않았다.

중요한 것은 이동 방법이 여러개인데 이를 어떻게 출력할 것인가 였다!

 

내가 결정한 방법은

1) 이동 방법과 이동했을 때 위치를 저장

2) 도착지점에서 세 가지 이동 방식을 활용해서 출발지점으로 이동하는 방법을 찾기 -> stack에 추가

3) 출력을 pop을 사용해서 해준다

였다.

 

사실 여러가지 이동 방법 중 하나의 이동 방법만 출력하면 되기에 가능한 시도였던 것 같다.

 

 

코드 :

from collections import deque

N, K = map(int, input().split())

# 방문 처리
visited = {}
# 이동 방향
dx = ['-', '+', '*']

queue = deque([N])
visited[N] = 0

move = []
while queue:
    now = queue.popleft()
    if now == K: break

    for i in dx:
        nx = now
        if i == '-': nx -= 1
        elif i == '+': nx += 1
        else: nx *= 2

        if 0<=nx<10**6+1 and nx not in visited:
            visited[nx] = visited[now] + 1
            queue.append(nx)
			
            # 이동 방법을 계산하기 위함
            if nx == now-1: move.append(('-', nx))
            elif nx == now+1: move.append(('+', nx))
            else: move.append(('*', nx))

move = move[::-1]

now = K # 도착 위치 -> 시작 위치 계산을 위함
answer = []
for i in move:
    if i[1] != now: continue
    answer.append(now)

    if i[0] == '-': now += 1
    elif i[0] == '+': now -= 1
    else: now = int(now/2)

answer.append(now) # 처음 시작 위치 추가

# output
print(visited[K])
while answer: print(answer.pop(), end=' ')
print()

 

 

 

사실 이렇게 하는게 맞나 조금 의심은 들지만.. 성공 !!!

뿌듯 !

 

 

'Programming > Algorithm' 카테고리의 다른 글

[백준3184] / 양 - BFS  (1) 2024.10.27
[백준1890] / 점프 - DP  (2) 2024.10.25
[백준9461] / 파도반 수열 - DP  (0) 2024.10.18
[백준2096] / 내려가기 - DP  (3) 2024.10.12
[백준7569] / 토마토 - BFS  (1) 2024.10.12
'Programming/Algorithm' 카테고리의 다른 글
  • [백준3184] / 양 - BFS
  • [백준1890] / 점프 - DP
  • [백준9461] / 파도반 수열 - DP
  • [백준2096] / 내려가기 - DP
__narrrrrmm
__narrrrrmm
__narrrrrmm
낢
__narrrrrmm
글쓰기 관리
전체
오늘
어제
  • 분류 전체보기 (71)
    • Programming (68)
      • Algorithm (61)
      • React JS (2)
      • SQL (5)
    • 낢의 하루 (1)
    • 대외활동 (1)

블로그 메뉴

  • 홈
  • 태그
  • 방명록

공지사항

인기 글

태그

SQL
mysql
heic
그래프탐색
삼성 금융아카데미
Dijkstra
Python
파이썬
컬럼별칭
DP
PCCP
MST
최소스패닝트리
프로그래머스
백트래킹
다이나믹프로그래밍
BFS
알고리즘
Javascript
그래프
DFS
백준
웹동아리
투포인터
다익스트라
React.js
백트레킹
누적합
파싱
StarRating
hELLO· Designed By정상우.v4.5.3
__narrrrrmm
[백준13913] / 숨바꼭질 4 - BFS
상단으로

티스토리툴바

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.