connecting the dots

문제 풀이 김대리가 회사에서 출발해 N명의 고객의 집에 방문한 뒤에 집까지 도착할 때까지의 경로 중 최소인 값을 구해야하는 문제이다. 김대리 기준으로 가까운 고객의 집부터 방문한다고 해서 최종 답이 나오는 것은 아니므로 주의해야 한다. N명 고객을 기준으로 순열을 만들어 모든 경우의 수를 따져본 뒤에 최종 답을 구해야 한다. 풀이 순서는 다음과 같다 N명의 고객을 기준으로해 N!개의 순열을 만들어 모든 경우를 따져본다 정해진 순서를 바탕으로 고객의 집에 방문한다 고객의 집에 방문할 때마다 거리를 count 해주고 김대리의 위치도 옮겨준다 고객의 집에 모두 방문하고 나면 김대리 집까지의 최소 경로도 더해준다 다음 순서로 경로를 구하기 위해 김대리의 위치를 처음 위치로 돌려놓는다 모든 순열에 대해 2~6번을..

문제 www.acmicpc.net/problem/17135 17135번: 캐슬 디펜스 첫째 줄에 격자판 행의 수 N, 열의 수 M, 궁수의 공격 거리 제한 D가 주어진다. 둘째 줄부터 N개의 줄에는 격자판의 상태가 주어진다. 0은 빈 칸, 1은 적이 있는 칸이다. www.acmicpc.net 풀이 바로 이전에 풀었던 아기상어 문제와 상당히 비슷했다 - 처음 설계 고려해야 하는 부분 궁수들은 같은 적을 공격할 수 있다 / 모든 궁수는 동시에 공격한다 - 첫 번째 궁수가 공격할 적을 바로 삭제해버리면 두 번째 궁수가 공격할 적이 바뀔 수도 있다. 따라서 각 궁수가 공격할 적을 모두 정한 다음에 한 번에 공격해야 한다 코드 import java.io.BufferedReader; import java.io.In..

문제 www.acmicpc.net/problem/16236 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가 www.acmicpc.net 풀이 fish라는 클래스를 만들어 물고기의 위치와 아기상어로부터 떨어져있는 거리를 저장할 수 있도록 해준다 아기상어의 위치부터 BFS를 사용해 물고기까지의 거리를 구한다/ 이 때 아기상어의 크기보다 큰 물고기는 지나가지 못하고 continue한다 / 아기상어의 크기보다 작은 물고기의 위치정보와 거리정보를 fish type으로 큐에 넣어 저장해둔다 BFS가 끝나면 먹을 수 있는 물고기 리스트가 들어있..

문제 풀이 이렇게 1초에 한 칸씩 이동할 때는 bfs를 사용한다 / 물이 넘칠 때도 bfs를 사용했다 고슴도치가 먼저 이동하고 물이 차도록 구현해서 고슴도치가 이동할 때 물이 이미 있는 곳 / 물이 찰 예정인 곳은 이동하지 않도록 했는데 굳이 이렇게 안 해도 물이 먼저 차고 고슴도치가 이동하면 물이 이미 있는 곳만 고려해주면 된다 물이 찰 예정인 곳까지 고려하느라 비버의 굴에 거의 다 왔을 때 물이 바로 옆에 있으면 이동하지 못하는 문제가 생겼다 / 이동할 곳이 비버의 굴이면 물이 옆에 있어도 이동할 수 있도록 비버의 굴인지 여부를 먼저 따져주었다 코드 import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.Lin..