https://www.acmicpc.net/problem/2178
[DFS,BFS] 백준 1260번 BFS와 DFS(C++)
[DFS,BFS] 백준 1260번 BFS와 DFS(C++)
https://www.acmicpc.net/problem/1260BFS와 DFS라는 개념에 대해서 아는가? 예제를 통한 예시를 보여주겠다 먼저 1,2 1,3 1,4 2,4 3,4라는 edge가 있는 경우를 그래프로 나타내보겠다 대략 이렇게 그려져 있다 그
lee-soo.tistory.com
bfs로 풀어야 되는 문제이다
지나야 하는 최소의 칸 수를 입력하라 했고,
그걸 bfs로 찾아가는 문제~
dfs로 하면 가장 깊은 방법으로 가기때문에
예를들어
1 1 1
1 1 1
1 1 1
이 있을경우
00 > 01 >02> 12 >11> 10 >20 >21 >>22로 아마 9번을 거쳐야 될 수도 있기에..
bfs로 찾아가는 문제이다!
어옷
앞서서 다른 bfs를 풀었을때는 이제 1차원 배열로 생각해서 풀었는데 그건 좀 비효율 적인거 같아서 이번엔 pair를 이용한 vector와 queue를 사용할 것이다.
풀이 내용은 대동소이 하지만 우리가 풀던것과는 다르게
1.모든 숫자는 붙어있고
2.00에서 n-1 m-1까지의 최소의 수를 구하라
이다.
모든 숫자는 붙어있으니
단 한번의 bfs만 진행되면 될 것이고
== (0,0)스타트
최소의 수를 구하라?
나는 여기서 dp를 생각햇다
그 전 것들에서 +1만 해가면 되지 않은가?
예를들어
1 | 1 | 1 | 1 |
1 | 0 | 1 | 0 |
0 | 1 | 1 | 1 |
1 | 0 | 0 | 1 |
1 | 1 | 1 | 1 |
이런 배열이 있다고 치자
그럼 여기서 첫번째에서 마지막인덱스로 가는 방법은?
이런 방법일 것이다
그리고 bfs가 숫자를 찾아가는 방식을 생각해보자
첫번째 인덱스에 대해서는 파란색으로 칠한 색깔을 먼저 찾고
그 이후는
그 이후는
뭔가 느낌이 오는가?
파란색으로 칠한 부분까지의 최소 거리는, 그저 부모 노드 + 1일 뿐인 것이다
그래서 자동으로 부모 노드 + 1은 그 거리까지의 최소가 되는 것이다.
자동으로 최소가 되는것을 알면 될 것이다.
'코딩 테스트 준비! (백준) > BFS' 카테고리의 다른 글
[BFS] 백준 7562번 나이트의 이동(C++) (0) | 2025.04.30 |
---|---|
[BFS] 백준 7576번 토마토(C++) (0) | 2025.04.24 |
[BFS] 백준 4963번 섬의 개수(C++) (0) | 2025.04.23 |
[BFS] 백준 2667번 단지 번호 붙이기(C++) (0) | 2025.04.23 |
[BFS] 백준 1707번 이분 그래프(C++) (0) | 2025.04.22 |