https://www.acmicpc.net/problem/2146
https://lee-soo.tistory.com/39
[DFS,BFS] 백준 1707번 이분 그래프(C++)
https://www.acmicpc.net/problem/1707 장난 아니다.이게 무슨 문제인것인가...예시를 봐도 이해가 안간다... [DFS,BFS] 백준 1260번 BFS와 DFS(C++)앞선 dfs와 bfs를 꼭 풀고오길 https://hongjw1938.tistory.com/117 자료구조 -
lee-soo.tistory.com
문제만 봐도~
이분 그래프 느낌이..?!
근데 저기 나오는 정치인 참 너무하네
1개만 세워준다니
쨋든
1. 각 섬이 존재
2. 각 섬을 잇는 다리 중 최소한의 다리의 길이 구하기
이다
내가 먼저 생각한건
1. 각 섬의 라벨링 ( 1이면 1 2이면 2.. )
2. 라벨링한 섬들간의 거리를 구하기 ( 각 섬마다 )
라벨링 하는건 앞선 이분 그래프 할 때 처럼 하면 되겠지?

이 입력에대해서
이렇게 섬마다 라벨링이 붙게 된다

label이 붙어있는데 이게 자신의 label이 아닐때는? 도착!

그럼 이때는 이 전 값에서 온 dp값을 출력하면 된다잉
어 근데 이거
어디서 많이 봤는데...
[DFS,BFS] 백준 7576번 토마토(C++)
https://www.acmicpc.net/problem/7576 멋쟁이 토마토 토마토 내용은 쉽다1의 번짐이지 퉁퉁퉁퉁퉁사후르 같은거 기대하고 토마토그려달라햇는데토마토가 토마토를 먹는 그림이 나옴무서워 잡설은 그만
lee-soo.tistory.com
뭔가 토마토 문제하고 비슷하지 않나?
여기서
dp[nx][ny] = dp[nx - dx[i]][ny - dy[i]] + 1;
이런식으로 퍼트려 나갔었고,
각 점에 대해서는 최소인 것이 확정된다고 설명했었다
쨋든
if (label[nx][ny] != 0 && label[nx][ny] != lab_c)
이게무슨뜻이냐?
해당 값이 0이 아니고, 또한 자신의 라벨링 값도 아니야.. 그렇다면!!
다른섬에 도착한거겠죠?
뭐... 어렵다~
'코딩 테스트 준비! (백준) > BFS' 카테고리의 다른 글
[BFS] 백준 13913번 숨바꼭질 4 (C++) (0) | 2025.05.08 |
---|---|
[BFS] 백준 1697번 숨바꼭질(C++) (0) | 2025.05.08 |
[BFS] 백준 16940 BFS 스폐셜 저지(C++) (0) | 2025.05.02 |
[BFS] 백준 7562번 나이트의 이동(C++) (0) | 2025.04.30 |
[BFS] 백준 7576번 토마토(C++) (0) | 2025.04.24 |