백준 16236 풀이?
https://www.acmicpc.net/problem/16236
아기상어
n*n 매트릭스가 주어지고 아기상어의 위치에서 물고기를 찾아가야하는 문제로 보아 bfs로 풀어야한다는 생각이 들었다.
처음에는 평소하던 방식대로 bfs를 적용해서 풀이를 했으나 만족해야하는 조건이 많고 까다로워 점점 산으로가는 기분이 들었다.
그래서 코드를 다 지우고 다시 처음부터 생각했다.
핵심은 현재 상어의 위치에서 먹을 수 있는 물고기의 최단 거리를 찾는 것이다.
이게 다시 생각한 내 결론이다.
처음에는 그냥 bfs에서 먼저 찾은 먹을 수 있는 물고기를 우선해서 먹고 다음 물고기를 찾아갔다면 문제에서는 최단거리이고 거리가 같은 경우 조건이 추가되었기 때문에 정답을 찾을 수가 없다.
따라서 간단하게 조건들을 정리해보자면
- 입력받은 값에서 9을 찾아 상어의 위치를 개별적인 변수에 저장한다.(sX, sY)
- 더 이상 먹을 물고기를 찾지 못 할때까지 탐색해야 하기때문에 while문 안에서 bfs를 시작한다.
- bfs를 시작하기전 while문 내에서 최소값을 저장할 변수들을 초기화해준다.(minX, minY, minDist, visit[][])
3-1. 이유는 물고기를 찾아 먹고 나면 해당 위치부터 다시 먹이를 찾아야 하기때문에 모두 초기화해줘야 한다.
3-2. 따라서 초기화하기 전 minX, minY의 값으로 상어의 위치를 바꿔줘야한다. - bfs 내부에서 모든 좌표를 다 돌아보고 조건들을 만족한다면 minX, minY 등을 갱신해준다. visit[][]의 값을 옮기기 전 위치의 값에서 1 더한 값으로 갱신해주면 방문체크 또한 동시에 가능하다.
- 모든 좌표의 탐색이 끝났다면 이제 상어가 성장할 수 있는지 체크하고 걸린 시간을 ans에 더해준다.
위의 방식으로 코드가 동작해야 할 것이라고 생각한다.
많은 조건들이 있어 많이 까다로웠고 구현하기에는 어려웠던 문제였다. 실제로 문제를 풀다 막혀 약간의 힌트를 보고 풀어낼 수 있었다.
아직 이런 응용, 심화 문제를 풀기에는 기초가 부족했다고 생각되어 다시 기초 개념 문제를 우선으로 풀고 다시 풀어볼 생각이다.
import java.io.*;
import java.util.LinkedList;
import java.util.Queue;
public class Main {
static int[] dx = {0, 0, -1, 1};
static int[] dy = {1, -1, 0, 0};
static int visit[][];
static int n, s;
static int graph[][];
static int age = 2;
static int count = 0;
static int ans = 0;
static int sX, sY;
static int minX;
static int minY;
static int minDist;
static int iii = 0;
public static void main(String[] args) throws IOException {
// write your code here
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
String num = br.readLine();
n = Integer.parseInt(num);
graph = new int[n][n];
for (int i = 0; i < n; i++) {
String[] tmp = br.readLine().split(" ");
for (int j = 0; j < n; j++) {
graph[i][j] = Integer.parseInt(tmp[j]);
if (graph[i][j] == 9) {
sX = i;
sY = j;
graph[sX][sY] = 0;
}
}
}
while (true) {
//초기화 하는 이유는 상어가 이동한 위치에서부터 dist를 계산해야 하기때문
visit = new int[n][n];
minX = Integer.MAX_VALUE;
minY = Integer.MAX_VALUE;
minDist = Integer.MAX_VALUE;
bfs(sX, sY);
if(minX != Integer.MAX_VALUE && minY != Integer.MAX_VALUE){
count++;
ans = ans + visit[minX][minY];
if(count == age){
age++;
count = 0;
}
graph[minX][minY] = 0;
sX = minX;
sY = minY;
}
else
break;
System.out.println("end");
}
System.out.println();
bw.write(ans + "\n");
br.close();
bw.close();
}
private static void bfs(int x, int y) {
Queue<Pair> queue = new LinkedList<>();
queue.add(new Pair(x, y));
while (!queue.isEmpty()) {
Pair p = queue.poll();
for (int i = 0; i < 4; i++) {
int newX = p.x + dx[i];
int newY = p.y + dy[i];
//이동 가능한지 검사
if ((newX >= 0 && newX <= n - 1) && (newY >= 0 && newY <= n - 1)) {
if (graph[newX][newY] <= age && visit[newX][newY] == 0) {
visit[newX][newY] = visit[p.x][p.y] + 1;
// 해당 위치 물고기 먹을 수 있는지 검사
if (graph[newX][newY] < age && graph[newX][newY] != 0) {
if (minDist > visit[newX][newY]) {
minDist = visit[newX][newY];
minX = newX;
minY = newY;
} else if (minDist == visit[newX][newY]) {
if (minX == newX) {
if (minY > newY) {
minX = newX;
minY = newY;
}
} else {
if (minX > newX) {
minX = newX;
minY = newY;
}
}
}
}
System.out.println(newX+" "+ newY+" ");
queue.add(new Pair(newX, newY));
}
}
}
}
}
}
class Pair {
public int x;
public int y;
public Pair(int x, int y) {
this.x = x;
this.y = y;
}
}
Author And Source
이 문제에 관하여(백준 16236 풀이?), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@estry/백준-16236-풀이저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)