[JAVA][백준 16236] 아기상어
- 알고리즘
- 2021. 3. 30.
SHORTCUT
반응형
| 사이트명 | 백준 |
| 문제 링크 | www.acmicpc.net/problem/16236 |
| 주요 알고리즘 | 시뮬레이션, BFS, |
| 사용 언어 | Java 자바 |
| 알고리즘이 낯선 사람들을 위해 생각 노트를 같이 두었습니다. |
|
1. 문제
2. 입력 / 출력
3. 풀이
3-1. 생각 노트
골드4의 아기상어 문제.
일단 삼성의 주요 기출 형태(구현) 중 하나이다. 조합같은 개념이 적용되진 않아서 어려운 편은 아니다.
그저 문제를 잘 읽고, 그대로 잘 구현 하면 된다.
3-2. 변수명
| 변수명 | 설명 |
| Class Fish | 물고기들의 시간값(거리)를 기록하기 위한 객체 |
|
ArrayList<Fish> feedList |
식사 가능한 경우 들어가는 후보 먹이 리스트! 추후 정렬을 통해 어느것을 먹을지 결정한다. |
|
Queue<Fish> q |
이동 가능한 경우에 들어가는 이동 대기열! |
3-3. 코드 보기
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.LinkedList;
import java.util.Queue;
public class BOJ16236_아기상어 {
// 먹이가 될 물고기
private static class Fish {
int x, y, time;
public Fish(int x, int y, int time) {
super();
this.x = x;
this.y = y;
this.time = time;
}
}
static int N;
static int[][] map;
static boolean[][] isVisit;
static Fish shark; // 상어도 물고기! 상어의 위치를 기록
static int size = 2;
static int eaten = 0;
static ArrayList<Fish> feedList = new ArrayList<>();
static int answer;
static int[] dx = {-1, 1, 0, 0};
static int[] dy = {0, 0, -1, 1};
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] input = br.readLine().split(" ");
N = Integer.parseInt(input[0]);
map = new int[N][N];
isVisit = new boolean[N][N];
for (int i = 0; i < N; i++) {
input = br.readLine().split(" ");
for (int j = 0; j < N; j++) {
map[i][j] = Integer.parseInt(input[j]);
if(map[i][j] == 9) {
shark = new Fish(i, j, 0);
map[i][j] = 0;
}
}
}
simulation();
System.out.println(answer);
}
private static void simulation() {
Queue<Fish> q = new LinkedList<>();
q.add(shark);
isVisit[shark.x][shark.y] = true;
while(true) {
while(!q.isEmpty()) {
Fish now = q.poll();
int time = now.time;
for (int k = 0; k < 4; k++) {
int nx = now.x + dx[k];
int ny = now.y + dy[k];
// 범위 밖 -> 아웃
if(!(0 <= nx && nx < N && 0 <= ny && ny < N) || isVisit[nx][ny]) continue;
// [식사 가능] 먹이 리스트에 추가
if(map[nx][ny] < size && map[nx][ny] != 0) {
q.add(new Fish(nx, ny, time+1));
isVisit[nx][ny] = true;
feedList.add(new Fish(nx, ny, time+1));
}
// [이동만 가능] 사이즈랑 동일 OR 비어있음(0)
if(map[nx][ny] == size || map[nx][ny] == 0) {
q.add(new Fish(nx, ny, time+1));
isVisit[nx][ny] = true;
}
}
}
if(!feedList.isEmpty()) {
eat();
// 식사가 끝났으면, 방문 배열 초기화
q.clear();
isVisit = new boolean[N][N];
// 다시 이동하는 큐(q)에다가 현재 상어 추가
q.add(shark);
isVisit[shark.x][shark.y] = true;
}else {
return;
}
}
}
// 먹이 리스트가 값이 존재하면, 식사 시작
private static void eat() {
// 정렬을 통해 우선순위별로 먹이 리스트 재정렬
Collections.sort(feedList, new Comparator<Fish>() {
@Override
public int compare(Fish o1, Fish o2) {
if(o1.time == o2.time) {
if(o1.x == o2.x) {
if(o1.y > o2.y) {
return 1;
}else {
return -1;
}
}else {
if(o1.x > o2.x) {
return 1;
}else {
return -1;
}
}
}else if(o1.time > o2.time){
return 1;
}else {
return -1;
}
};
});
Fish now = feedList.get(0);
// 상어 위치 이동, 상어가 먹은 횟수 증가, 상어 걸린 시간 증가
shark.x = now.x;
shark.y = now.y;
if(++eaten == size) {
size++;
eaten = 0;
}
answer += now.time;
// 지도 위에 해당 위치 0 처리
map[now.x][now.y] = 0;
// 먹이 리스트 초기화
feedList.clear();
}
}
3-4. 마무리
이전에 한번 푼 문제였는데, 다시 푸니 틀렸다...
틀린 이유 분석
- BFS를 수행할 때, time+1로 시간값이 증가하므로 4방 탐색을 하는 단계마다 먹이 리스트에 넣으면 거리(시간)계산을 안해도 되겠다는 생각으로 접근
- 하지만, 몇몇 값에선, time값이 늦게 반영되어 동일한 시간값이지만 체킹을 못하고 넘어가는 경우가 발생..
- 아, 식사 가능한 경우에도 먹이 리스트에 넣고 + 이동 Q에도 넣어야 한다. 이부분 살짝 애매하면 꼬인다.
따라서, 로직 자체를 while로 무한루프를 만들고 [BFS 탐색 -> 식사] 를 반복하는 형태로 변경
BFS는 BFS로만 두고, 로직을 끼우지 말자. 딱 탐색이라는 기능만 구현해두는게 맞다.
아.
이전 코드를 다시 보는데, 내가 썼던 변수명이나 스타일이 똑같았다..
역시 사람 안변한다는 걸 느낀다.. 아니, 변하진 않고 더 발전하겠지..
반응형