Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |
Tags
- level3
- 파이썬
- 구현
- level2
- BOJ
- 힙
- python
- level0
- N과M
- 다이나믹 프로그래밍
- programmers
- 다익스트라
- DP
- dfs
- MYSQL
- 딕셔너리
- 프로그래머스
- 브루트포스
- 재귀
- 수학
- 코딩테스트
- dict
- 스택
- 그리디
- 가상메모리
- 가상메모리 관리
- 백준
- level1
- BFS
- 운영체제
Archives
- Today
- Total
동캄의 코딩도장
백준 16928 [뱀과 사다리 게임] 파이썬 DFS BFS 본문
https://www.acmicpc.net/problem/16928
맨 처음에는 위 문제를 dp를 이용해서 해결하려고 하였으나 실패하였다.
# 백준 16928 DFS
import sys
sys.setrecursionlimit = 10**6
N, M = map(int, input().split())
ladder = {}
snake = {}
for _ in range(N):
a, b = map(int, input().split())
ladder[a] = b
for _ in range(M):
a, b = map(int, input().split())
snake[a] = b
visited = [100000]*(101)
global answer
answer = 100000
def dfs(num):
global answer
if num == 100:
answer = min(answer, visited[num])
if num in ladder:
if visited[ladder[num]] > visited[num]:
visited[ladder[num]] = visited[num]
dfs(ladder[num])
elif num in snake:
if visited[snake[num]] > visited[num]:
visited[snake[num]] = visited[num]
dfs(snake[num])
else:
for i in range(6, 0, -1):
if num+i <= 100:
if visited[num+i] > visited[num]+1:
visited[num+i] = visited[num]+1
dfs(num+i)
visited[1] = 0
dfs(1)
print(answer)
# 백준 16928 BFS
from collections import deque
import sys
N, M = map(int, input().split())
ladder = {}
snake = {}
for _ in range(N):
a, b = map(int, input().split())
ladder[a] = b
for _ in range(M):
a, b = map(int, input().split())
snake[a] = b
visited = [0]*(101)
global answer
answer = 100000
visited = [10000]*(101)
def bfs(num):
global answer
q = deque([])
q.append(num)
while q:
num = q.popleft()
if num == 100:
answer = visited[100]
else:
if num in ladder:
if visited[ladder[num]] > visited[num]:
visited[ladder[num]] = visited[num]
q.append(ladder[num])
elif num in snake:
if visited[snake[num]] > visited[num]:
visited[snake[num]] = visited[num]
q.append(snake[num])
else:
for i in range(6, 0, -1):
if num+i <= 100:
if visited[num+i] > visited[num]+1:
visited[num+i] = visited[num]+1
q.append(num+i)
visited[1] = 0
bfs(1)
print(answer)
DFS와 BFS의 원리는 같다. 그 점에서 최솟값을 갱신하면 계속 탐색하고, 그렇지 않다면 탐색을 멈추는 것이다.
'코테 > BOJ' 카테고리의 다른 글
백준 14502 [연구소] 파이썬 (0) | 2022.04.15 |
---|---|
백준 7569 [토마토] 파이썬 (0) | 2022.04.15 |
백준 14500 [테트로미노] 파이썬 (0) | 2022.04.14 |
백준 10026 [적록색약] 파이썬 (0) | 2022.04.14 |
백준 5430 [AC] 파이썬 (0) | 2022.04.12 |