교대최소제곱법
[코테준비] BFS, 0-1 BFS 본문
BFS 너비우선탐색 문제
최단거리를 구할때 사용
가장 먼저 찾아내는게 최단거리이다 -> BFS 사용이유
시간복잡도
N이 노드의 개수, E가 간선의 개수일 때
인접 리스트: O(N + E)
인접 행렬: O(N^2)
예제 풀이 프로세스
deque을 사용
- 입력값 받기
- 그래프크기
N, M = map(int, input().split()) - 그래프 모양
board = [list(map(int,input().split())) for _ in range(N)]
- 그래프크기
- 볼 위치파악
- for i for j append 구문으로 현위치를 파악하고
- from collection import deque에 넣어놓는다
- 방문여부를 기억하려면 넣어두기 visited[i][j] = 1
- 이거로 장난 칠수도 있다
기억했다가 안했다가를 바꾸는 문제도 있다
- 이거로 장난 칠수도 있다
- 이때 카운트도 선언해둔다
- 탐색
- dx, dy를 활용해서 4방향을 for문으로 탐색
- 현재위치를 deque에서 뽑아온다
- 미래위치를 예상해본다
- 미래위치가 조건에 맞는지 확인
- 이때 추가조건들을 넣어준다
- 미래위치가 이미 방문한 곳이었는지 확인
- 다 ok이면 deque랑 방문기록에 입력
예제 문제
[BOJ] 백준 - 16236 아기상어 (파이썬)
백준 - 16236 아기상어 (파이썬)
velog.io
백준 알고리즘 13460: 구슬 탈출 2 (Python)
백준 알고리즘 13460: 구슬 탈출 2 (Python)
www.acmicpc.net/problem/13460 13460번: 구슬 탈출 2 첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열
bgspro.tistory.com
+
0-1 bfs
13549번: 숨바꼭질 3
수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때
www.acmicpc.net
-> 모든 거리가 0 또는 1인 경우 사용
이건 시간복잡도가 O(V+E)이다
가장 먼저 찾아내는게 최단거리 맞긴한데
위의 문제처럼 + - 의 순서를 주의해서 deque에 넣을 필요가 있음 -> 우선순위를 고려해야한다는 뜻
거리합이 0일때 큐를 앞쪽에 넣어주는게 포인트
[algorithm] 0-1 BFS
0-1 BFS는 가중치가 0, 1로 주어진 그래프에서 최단경로를 찾아낼 수 있는 알고리즘입니다. 최단경로 알고리즘에는 다익스트라 알고리즘을 사용할 수 있지만, 시간 복잡도가 O(ElogE) 또는 O(ElogV)인
velog.io
'코딩테스트' 카테고리의 다른 글
| [코테준비] 순열, 조합, 백트래킹 (0) | 2023.09.11 |
|---|---|
| [코테준비] 분할정복, DP, 그리디 (0) | 2023.09.09 |
| [코테준비] 다익스트라 알고리즘, 벨만-포드 알고리즘 (0) | 2023.09.09 |
| [코테준비] DFS (0) | 2023.09.09 |
| [코테준비] 시간 복잡도를 고려하자 (0) | 2023.09.09 |
