부르트포스 (2) 썸네일형 리스트형 백준 17472번(JAVA) 이번에 푼 문제는 크게 3가지 단계를 걸치면 된다. 1.섬별로 번호 붙이기 2.섬간의 다리(간선)정보 넣기 3. 2번을 통해 나온 섬간의 간선정보를 바탕으로 프림알고리즘을 수행하여 최소스패닝트리, 즉 각 섬을 모두 연결하는데 필요한 최소한의 비용을 구한다. 섬별로 번호를 붙이는건 어렵지 않다. 0이아닌 땅을 밟으면 BFS를 실행해주어 연결된 모든 1을 한 섬으로 지정한다 이 때 변수 islans_cnt변수가 BFS를 실행할때마다 +되어서 번호를 붙여준다. 그 후 섬간의 다리 정보를 입력받는데 꽤나 까다로운 조건이 붙어있다. 그렇기에 그점에 잘 유의해서 if문을 작성해준다 필자는 오른쪽,왼쪽,아래쪽,위쪽 4개의 for문을 사용했는데 이걸 한 개의 for문으로 줄일 수 있으면 좋겠다. 마지막으로 프림알고리즘.. 백준 15686번(JAVA) brute force 문제이다. 시간초과때문에 몇 번이고 다시 풀었던 문제이다. 시간초과를 피하며 구현을 잘하면 된다 이 문제의 핵심은 3가지라고 생각한다. 지도를 입력받으며 치킨집과 가정집의 위치를 미리 선언한 ArrayList에 넣는다. ArrayList를 사용함으로써 지도 전체를 탐색하며 거리를 계산하는게 아니라 ArrayList에서 각각 꺼내와서 거리를 계산한다. 이러면 시간을 훨씬 단축시킬 수 있다. 치킨집 ArrayList에서 M개의 치킨집을 고르는것은 backtrack으로 구현한다. 만약 백트랙하다가 치킨집의개수가 M개가 되면 바로 DFS()함수를 호출해서(이름은 그냥 막 지었다) M개의 치킨집에대한 치킨거리를 구한다. Backtrack을 할때 재귀함수로 호출하는데 호출할때 시작점은 이전에 .. 이전 1 다음