문제 설명
아기 상어 뚜루뚜루 문제의 링크는 여기.
문제의 조건을 간단히 정리하면 다음과 같다.
- N*N 크기의 맵, 아기 상어 1마리와 물고기들
- 아기 상어는 자신보다 작은 물고기를 먹을 수 있음
- 아기 상어는 초당 상하좌우 4방향으로 한칸 이동 가능
- 아기 상어는 자신의 크기 만큼 물고기를 먹으면 크기가 1 증가
- 아기 상어는 빈칸(0) 혹은 자신과 같은 크기의 물고기를 지날 수 있음
- 아기 상어는 가장 가까운 물고기를 먼저 먹음
- 이때 여러 마리가 존재하면 최상단, 최좌즉 물고기를 우선 먹음
- 더 이상 접근할 수 있는 물고기가 없으면 도움 요청, 이 때의 시간을 출력
접근
시도 1
처음에는 상하좌우 이동을 아래의 조건을 고려하여 짠다면 bfs로 아주 간단히 풀 수 있지 않을까? 에서 시작하였다.
public class Main {
// 순서대로 상, 좌, 우, 하 순으로 탐색
public static int[] dr = {-1, 0, 0, 1};
public static int[] dc = {0, -1, 1, 0};
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// 입력 처리 부분
int N = Integer.parseInt(br.readLine());
StringTokenizer st;
int[][] arr = new int[N+2][N+2];
for(int i=0; i<N+2; i++) {
arr[0][i] = Integer.MAX_VALUE;
arr[N+1][i] = Integer.MAX_VALUE;
arr[i][0] = Integer.MAX_VALUE;
arr[i][N+1] = Integer.MAX_VALUE;
}
int y=0, x=0;
for(int r=1; r<=N; r++) {
st = new StringTokenizer(br.readLine());
for(int c=1; c<=N; c++) {
arr[r][c] = Integer.parseInt(st.nextToken());
if(arr[r][c]==9) {
y = r;
x = c;
arr[r][c] = 0;
}
}
}
// bfs 부분
Queue<int[]> queue = new LinkedList<int[]>();
queue.add(new int[] {y, x, 0});
// 초기 상어 상태 저장
int size = 2;
int amount = 2;
int t = 0;
boolean[][] visited = new boolean[N+2][N+2];
visited[y][x] = true;
while(!queue.isEmpty()) {
int[] temp = queue.poll();
// 먹을 수 있는 물고기 발견 시 먹기
if(arr[temp[0]][temp[1]]>0 && arr[temp[0]][temp[1]]<size) {
arr[temp[0]][temp[1]] = 0;
// 시간 업데이트
t = temp[2];
// 성장까지 남은 물고기 수 -1
amount--;
// 충족했다면 성장!
if(amount==0) {
size++;
amount = size;
}
// 새로운 위치에서 다시 탐색 시작
queue.clear();
visited = new boolean[N+2][N+2];
visited[temp[0]][temp[1]] = true;
}
// 추가할 때 요구 조건을 충분히 고려했다고 생각함...
for(int i=0; i<4; i++) {
int r = temp[0] + dr[i];
int c = temp[1] + dc[i];
if(!visited[r][c] && arr[r][c]<=size) {
queue.add(new int[] {r, c, temp[2]+1});
visited[r][c] = true;
}
}
}
System.out.println(t);
}
}위의 코드의 경우 예상치 못한 변수가 있었다. 이는 탐색 순서를 고려하면 찾을 수 있는 반례이다.
위의 그림에서 X는 지나갈 수 없는 곳, 숫자는 코드 상 탐색 순서이다. 같은 색상의 칸은 같은 도달하는 데 같은 시간이 걸린다.
4, 6에 모두 물고기 있다고 가정하자. 이 경우 정답은 6번의 물고기에게 가야하나 코드 상 4번의 물고기를 먹게 된다. 따라서 이러한 접근 방식은 해답이 아니다.
시도 2
그렇다면 어떻게 접근하는게 좋을까? 가장 쉬운 방법은 같은 거리를 모두 확인하고 이후 갈 곳을 결정하면 된다.
같은 거리내 위치를 탐색하는 동안, 답이 될 수 있는 위치를 저장한다. 이후 같은 거리의 모든 위치를 확인한 후 최상단, 최우측의 먹이를 골라 먹으면 된다. 코드는 다음과 같이 수정하였다.
private static int bfs(int Y, int X, int N, int[][] arr) {
Queue<int[]> queue = new LinkedList<int[]>();
// 초기 아기 상어의 위치를 삽입
queue.add(new int[] {Y, X, 0});
// 초기 아기 상어 설정
int size = 2;
int amount = 2;
// 먹을 먹이 세이브용 파라미터
int[] save = null;
int time = 0;
boolean[][] visited = new boolean[N+2][N+2];
visited[Y][X] = true;
while(!queue.isEmpty()) {
int[] temp = queue.poll();
int y = temp[0], x = temp[1], t = temp[2];
// 단순 길인 경우
if(arr[y][x]==0 || arr[y][x]==size) {
for(int i=0; i<4; i++) {
if(save!=null) break;
int r = y + dr[i];
int c = x + dc[i];
if(!visited[r][c] && arr[r][c]<=size) {
queue.add(new int[] {r, c, temp[2]+1});
visited[r][c] = true;
}
}
}
// 먹이 발견 시 저장 시도
else {
if(save==null || save[0]>y || (save[0]==y && save[1]>x))
save = temp;
}
// 가장 가까운 먹이가 결정된 경우
if(save!=null && (queue.isEmpty() || queue.peek()[2]>t)) {
y = save[0]; x = save[1]; t = save[2];
time = t;
save = null;
// 먹음 표시
arr[y][x] = 0;
visited = new boolean[N+2][N+2];
visited[y][x] = true;
queue.clear();
queue.add(new int[] {y, x, t});
// 크기가 커지기 위해 먹어야하는 물고기 수 감소
amount--;
// 커졌으면 amount 값 초기화
if(amount==0)
amount = ++size;
}
}
return time;
}소스코드
최종적으로 제출한 코드는 다음과 같다.
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main {
// 4방향 탐색 시 사용할 배열
public static int[] dr = {-1, 0, 0, 1};
public static int[] dc = {0, -1, 1, 0};
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
StringTokenizer st;
int[][] arr = new int[N+2][N+2];
// arr 범위 검사 부분을 스킵하기 위해 테두리 부분을 지정
for(int i=0; i<N+2; i++) {
arr[0][i] = Integer.MAX_VALUE;
arr[N+1][i] = Integer.MAX_VALUE;
arr[i][0] = Integer.MAX_VALUE;
arr[i][N+1] = Integer.MAX_VALUE;
}
int y=0, x=0;
// 입력에 맞게 arr에 데이터 삽입
for(int r=1; r<=N; r++) {
st = new StringTokenizer(br.readLine());
for(int c=1; c<=N; c++) {
arr[r][c] = Integer.parseInt(st.nextToken());
// 아기 상어 위치인 경우 세이브
if(arr[r][c]==9) {
y = r;
x = c;
arr[r][c] = 0;
}
}
}
// bfs를 이용하여 탐색
System.out.println(bfs(y, x, N, arr));
}
private static int bfs(int Y, int X, int N, int[][] arr) {
Queue<int[]> queue = new LinkedList<int[]>();
// 초기 아기 상어의 위치를 삽입
queue.add(new int[] {Y, X, 0});
// 초기 아기 상어 설정
int size = 2;
int amount = 2;
// 먹을 먹이 세이브용 파라미터
int[] save = null;
int time = 0;
boolean[][] visited = new boolean[N+2][N+2];
visited[Y][X] = true;
while(!queue.isEmpty()) {
int[] temp = queue.poll();
int y = temp[0], x = temp[1], t = temp[2];
// 단순 길인 경우
if(arr[y][x]==0 || arr[y][x]==size) {
for(int i=0; i<4; i++) {
if(save!=null) break;
int r = y + dr[i];
int c = x + dc[i];
if(!visited[r][c] && arr[r][c]<=size) {
queue.add(new int[] {r, c, temp[2]+1});
visited[r][c] = true;
}
}
}
// 먹이 발견 시 저장 시도
else {
if(save==null || save[0]>y || (save[0]==y && save[1]>x))
save = temp;
}
// 가장 가까운 먹이가 결정된 경우
if(save!=null && (queue.isEmpty() || queue.peek()[2]>t)) {
y = save[0]; x = save[1]; t = save[2];
time = t;
save = null;
// 먹음 표시
arr[y][x] = 0;
visited = new boolean[N+2][N+2];
visited[y][x] = true;
queue.clear();
queue.add(new int[] {y, x, t});
// 크기가 커지기 위해 먹어야하는 물고기 수 감소
amount--;
// 커졌으면 amount 값 초기화
if(amount==0)
amount = ++size;
}
}
return time;
}
}결과
제출 결과는 다음과 같다.
고찰
솔직히 테케가 잘못된 걸 알려주기 전까지는 틀릴 줄도 몰랐다… 부랴부랴 코드를 수정했는데 예상치 못한 버그가 많이 생겨 디버깅에서 생각보다 시간을 많이 잡아먹혔다.
항상 느끼는 거지만, 나는 너무 문제를 신중하게 읽지 않는 것 같다. 조금만 더 생각해보고 코드를 작성했으면 더 빠르게 해결할 수 있지 않았을까 싶다…
오엥