반응형 컴퓨터 사이언스/BOJ42 [c++] 백준 #2146 다리만들기 https://www.acmicpc.net/problem/2146 백준문제 #7576 토마토 문제를 풀었다면 비슷하게 풀 수 있다.각 섬에서부터 바다로 뻗어나가면서 섬에서의 거리를 측정하다가, 다른 섬에서 이미 거리를 측정한 부분을 만나는 경우, 두 거리를 더해서 그 합의 최소값을 구하면 된다. 이때 각 섬이 어디있는 지, 사전에 labeling을 해둬야하기 때문에 DFS를 돌리고, 그 다음에 거리를 BFS를 이용해서 구하면 된다. DFS를 이용하여 각 섬에 대해 labeling하는 것은 백준문제 #2667 단지번호 붙이기를 풀었다면 그냥 그때 쓴 코드 재활용하면 된다. 123456789101112131415161718192021222324252627282930313233343536373839404142.. 2018. 10. 24. [c++]백준 #9466 텀프로젝트 https://www.acmicpc.net/problem/9466 1) DFS를 돌리면서 starting point부터 번호를 하나씩 매김(배열 dist 이용).2) DFS가 시작될 때마다 graph number를 새로 부여(변수 ng) 이용3) DFS를 돌다가 같은 그래프 내의 이미 방문한 점을 만나게 되면 그 점이 나오기 전까지의 노드는 cycle에 속하지 않으므로 cycle이 생기기 전까지의 노드의 개수를 배열 dist에 접근하여 더해줌e.g. 예시에서 1->3->3 순으로 노드를 방문하게 되는 경우 노드 1은 팀을 이루지 못함4) DFS를 돌다가 다른 그래프 내의 이미 방문한 점을 만나게 되면 그 전 노드까지 노드의 개수를 배열 dist에 접근하여 더해줌e.g. 예시에서 이미 1-.. 2018. 10. 24. 이전 1 ··· 8 9 10 11 다음 반응형