https://www.acmicpc.net/problem/7562
1. 생각해보기
1) 아이디어
최소 케이스를 찾는 문제라서 이 케이스는 BFS로 풀어야 함.
단, 이동 방향은 총 8가지 임. x와 y를 나눠서 8개 케이스를 저장하면 될 것 같음.
2) 시간복잡도
BFS 시간복잡도 O(V + E)
V = 300 * 300 = 90000(9만)
E = 8 * V(9만) = (72만)
O(9만 + 72만) = 81만 (1억미만임으로, 1초안에 계산 OK)
3) 자료구조
- 큐, 방문 배열
- head
2. 직접풀어보기
https://github.com/moonlight-duck/study-algorithms/pull/22
[민주] BFS 문제풀이 2 by min-99 · Pull Request #22 · moonlight-duck/study-algorithms
📌 문제 정보 문제 링크 : https://www.acmicpc.net/problem/7562 카테고리 (예: 구현, 탐색, DP) : BFS ✏️ 풀이 방법 결과 (성공/실패) : 성공 풀이 시간 : 7562 : study 10m cooding: 30m 풀이 방법 : https://min-99.tistory.c
github.com
결과)
'알고리즘' 카테고리의 다른 글
| DP 개념 (0) | 2025.11.11 |
|---|---|
| BFS(백준 : 토마토-7576문제) 접근 방법 (0) | 2025.10.30 |
| BFS(백준 : 숨바꼭질-1697문제) 접근 방법 (0) | 2025.10.30 |
| BFS(백준 : 미로탐색-2178문제) 접근 방법 (0) | 2025.10.29 |
| BFS(너비우선탐색) vs DFS(깊이우선탐색) (0) | 2025.10.29 |