NรN ํฌ๊ธฐ์ ๊ณต๊ฐ์ ๋ฌผ๊ณ ๊ธฐ M๋ง๋ฆฌ์ ์๊ธฐ ์์ด 1๋ง๋ฆฌ๊ฐ ์๋ค. ๊ณต๊ฐ์ 1ร1 ํฌ๊ธฐ์ ์ ์ฌ๊ฐํ ์นธ์ผ๋ก ๋๋์ด์ ธ ์๋ค. ํ ์นธ์๋ ๋ฌผ๊ณ ๊ธฐ๊ฐ ์ต๋ 1๋ง๋ฆฌ ์กด์ฌํ๋ค.
์๊ธฐ ์์ด์ ๋ฌผ๊ณ ๊ธฐ๋ ๋ชจ๋ ํฌ๊ธฐ๋ฅผ ๊ฐ์ง๊ณ ์๊ณ , ์ด ํฌ๊ธฐ๋ ์์ฐ์์ด๋ค. ๊ฐ์ฅ ์ฒ์์ ์๊ธฐ ์์ด์ ํฌ๊ธฐ๋ 2์ด๊ณ , ์๊ธฐ ์์ด๋ 1์ด์ ์ํ์ข์ฐ๋ก ์ธ์ ํ ํ ์นธ์ฉ ์ด๋ํ๋ค.
์๊ธฐ ์์ด๋ ์์ ์ ํฌ๊ธฐ๋ณด๋ค ํฐ ๋ฌผ๊ณ ๊ธฐ๊ฐ ์๋ ์นธ์ ์ง๋๊ฐ ์ ์๊ณ , ๋๋จธ์ง ์นธ์ ๋ชจ๋ ์ง๋๊ฐ ์ ์๋ค. ์๊ธฐ ์์ด๋ ์์ ์ ํฌ๊ธฐ๋ณด๋ค ์์ ๋ฌผ๊ณ ๊ธฐ๋ง ๋จน์ ์ ์๋ค. ๋ฐ๋ผ์, ํฌ๊ธฐ๊ฐ ๊ฐ์ ๋ฌผ๊ณ ๊ธฐ๋ ๋จน์ ์ ์์ง๋ง, ๊ทธ ๋ฌผ๊ณ ๊ธฐ๊ฐ ์๋ ์นธ์ ์ง๋๊ฐ ์ ์๋ค.
์๊ธฐ ์์ด๊ฐ ์ด๋๋ก ์ด๋ํ ์ง ๊ฒฐ์ ํ๋ ๋ฐฉ๋ฒ์ ์๋์ ๊ฐ๋ค.
๋ ์ด์ ๋จน์ ์ ์๋ ๋ฌผ๊ณ ๊ธฐ๊ฐ ๊ณต๊ฐ์ ์๋ค๋ฉด ์๊ธฐ ์์ด๋ ์๋ง ์์ด์๊ฒ ๋์์ ์์ฒญํ๋ค.
๋จน์ ์ ์๋ ๋ฌผ๊ณ ๊ธฐ๊ฐ 1๋ง๋ฆฌ๋ผ๋ฉด, ๊ทธ ๋ฌผ๊ณ ๊ธฐ๋ฅผ ๋จน์ผ๋ฌ ๊ฐ๋ค.
๋จน์ ์ ์๋ ๋ฌผ๊ณ ๊ธฐ๊ฐ 1๋ง๋ฆฌ๋ณด๋ค ๋ง๋ค๋ฉด, ๊ฑฐ๋ฆฌ๊ฐ ๊ฐ์ฅ ๊ฐ๊น์ด ๋ฌผ๊ณ ๊ธฐ๋ฅผ ๋จน์ผ๋ฌ ๊ฐ๋ค.
๊ฑฐ๋ฆฌ๋ ์๊ธฐ ์์ด๊ฐ ์๋ ์นธ์์ ๋ฌผ๊ณ ๊ธฐ๊ฐ ์๋ ์นธ์ผ๋ก ์ด๋ํ ๋, ์ง๋์ผํ๋ ์นธ์ ๊ฐ์์ ์ต์๊ฐ์ด๋ค.
๊ฑฐ๋ฆฌ๊ฐ ๊ฐ๊น์ด ๋ฌผ๊ณ ๊ธฐ๊ฐ ๋ง๋ค๋ฉด, ๊ฐ์ฅ ์์ ์๋ ๋ฌผ๊ณ ๊ธฐ, ๊ทธ๋ฌํ ๋ฌผ๊ณ ๊ธฐ๊ฐ ์ฌ๋ฌ๋ง๋ฆฌ๋ผ๋ฉด, ๊ฐ์ฅ ์ผ์ชฝ์ ์๋ ๋ฌผ๊ณ ๊ธฐ๋ฅผ ๋จน๋๋ค.
์๊ธฐ ์์ด์ ์ด๋์ 1์ด ๊ฑธ๋ฆฌ๊ณ , ๋ฌผ๊ณ ๊ธฐ๋ฅผ ๋จน๋๋ฐ ๊ฑธ๋ฆฌ๋ ์๊ฐ์ ์๋ค๊ณ ๊ฐ์ ํ๋ค. ์ฆ, ์๊ธฐ ์์ด๊ฐ ๋จน์ ์ ์๋ ๋ฌผ๊ณ ๊ธฐ๊ฐ ์๋ ์นธ์ผ๋ก ์ด๋ํ๋ค๋ฉด, ์ด๋๊ณผ ๋์์ ๋ฌผ๊ณ ๊ธฐ๋ฅผ ๋จน๋๋ค. ๋ฌผ๊ณ ๊ธฐ๋ฅผ ๋จน์ผ๋ฉด, ๊ทธ ์นธ์ ๋น ์นธ์ด ๋๋ค.
์๊ธฐ ์์ด๋ ์์ ์ ํฌ๊ธฐ์ ๊ฐ์ ์์ ๋ฌผ๊ณ ๊ธฐ๋ฅผ ๋จน์ ๋ ๋ง๋ค ํฌ๊ธฐ๊ฐ 1 ์ฆ๊ฐํ๋ค. ์๋ฅผ ๋ค์ด, ํฌ๊ธฐ๊ฐ 2์ธ ์๊ธฐ ์์ด๋ ๋ฌผ๊ณ ๊ธฐ๋ฅผ 2๋ง๋ฆฌ ๋จน์ผ๋ฉด ํฌ๊ธฐ๊ฐ 3์ด ๋๋ค.
๊ณต๊ฐ์ ์ํ๊ฐ ์ฃผ์ด์ก์ ๋, ์๊ธฐ ์์ด๊ฐ ๋ช ์ด ๋์ ์๋ง ์์ด์๊ฒ ๋์์ ์์ฒญํ์ง ์๊ณ ๋ฌผ๊ณ ๊ธฐ๋ฅผ ์ก์๋จน์ ์ ์๋์ง ๊ตฌํ๋ ํ๋ก๊ทธ๋จ์ ์์ฑํ์์ค.
์ ๋ ฅ
์ฒซ์งธ ์ค์ ๊ณต๊ฐ์ ํฌ๊ธฐ N(2 โค N โค 20)์ด ์ฃผ์ด์ง๋ค.
๋์งธ ์ค๋ถํฐ N๊ฐ์ ์ค์ ๊ณต๊ฐ์ ์ํ๊ฐ ์ฃผ์ด์ง๋ค. ๊ณต๊ฐ์ ์ํ๋ 0, 1, 2, 3, 4, 5, 6, 9๋ก ์ด๋ฃจ์ด์ ธ ์๊ณ , ์๋์ ๊ฐ์ ์๋ฏธ๋ฅผ ๊ฐ์ง๋ค.
0: ๋น ์นธ
1, 2, 3, 4, 5, 6: ์นธ์ ์๋ ๋ฌผ๊ณ ๊ธฐ์ ํฌ๊ธฐ
9: ์๊ธฐ ์์ด์ ์์น
์๊ธฐ ์์ด๋ ๊ณต๊ฐ์ ํ ๋ง๋ฆฌ ์๋ค.
์ถ๋ ฅ
์ฒซ์งธ ์ค์ ์๊ธฐ ์์ด๊ฐ ์๋ง ์์ด์๊ฒ ๋์์ ์์ฒญํ์ง ์๊ณ ๋ฌผ๊ณ ๊ธฐ๋ฅผ ์ก์๋จน์ ์ ์๋ ์๊ฐ์ ์ถ๋ ฅํ๋ค.
๐ก bfs๋ฅผ ํตํด ์ต์ ๊ฑฐ๋ฆฌ๋ฅผ ์ฐพ์
๋ฐฉ๋ฌธํ๋ ๊ณณ ๋ฐฉ๋ฌธํ์ง ์๊ธฐ
๋ฒ์๋ฅผ ๋ฒ์ด๋๋ ๊ณณ ๋ฐฉ๋ฌธํ์ง ์๊ธฐ
์์ด์ ํฌ๊ธฐ๋ณด๋ค ํฐ ๋ฌผ๊ณ ๊ธฐ๊ฐ ์๋ ๊ณณ์ผ๋ก ์ด๋ํ์ง ์๊ธฐ
์์ด์ ํฌ๊ธฐ์ ๊ฐ๊ฑฐ๋ ์๋ฌด๊ฒ๋ ์๋ ๊ณณ์ ๊ทธ๋ฅ ์ด๋ํ๊ธฐ
์์ด์ ํฌ๊ธฐ๋ณด๋ค ์์ ๋ฌผ๊ณ ๊ธฐ๋ ์ก์๋จน๊ณ ์ด๋ํ๊ธฐ
๐ก BFS๋ฅผ ํตํด ์ต์ ๊ฑฐ๋ฆฌ๋ฅผ ์ฐพ์ผ๋ฉด ๊ทธ ์์น์ ์๋ ๋ฌผ๊ณ ๊ธฐ๋ฅผ ๋จน๊ณ , ๊ทธ ์์น๋ก ์ด๋ํ๊ณ , time์ ๋๋ ค์ค (์ด๋ฅผ ์ก์๋จน์ ๋ฌผ๊ณ ๊ธฐ๊ฐ ์์ ๋๊น์ง ๋ฐ๋ณตํจ)
๐ก ๋ง์ผ ์์ด์ ํฌ๊ธฐ ๋งํผ ๋จน์๋ค๋ฉด ์์ด์ ํฌ๊ธฐ๋ฅผ ๋๋ ค์ค
static void bfs(int a, int b) {
Queue<Node> q = new LinkedList<>();
q.add(new Node(a,b));
while(!q.isEmpty()) {
Node cur = q.poll();
int x = cur.x;
int y = cur.y;
for(int i=0; i<4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
...
dist[nx][ny] = dist[x][y]+1;
...
q.add(new Node(nx,ny));
}
}
}
if(dist[nx][ny] != 0 || map[nx][ny] > babyShark)
continue;
if(nx < 0 || ny < 0 || nx >= n || ny >= n)
continue;
dist[nx][ny] = dist[x][y] + 1;
...
q.add(new Node(nx, ny));
๋จ์ด์ ธ ์๋ ๊ฑฐ๋ฆฌ๊ฐ ๋์ผํ๋ค๋ฉด, 1)์์ชฝ ๋จผ์ (x๊ฐ ์์์ชฝ), ๋์ผํ ๋์ด์ ์๋ค๋ฉด ์ผ์ชฝ(y๊ฐ ์์์ชฝ)๋จผ์ ์ก์๋จน๊ธฐ
if(map[nx][ny] != 0 && map[nx][ny] < babyShark) {
if(minDist > dist[nx][ny]) {
minDist = dist[nx][ny];
minX = nx;
minY = ny;
} else if(minDist == dist[nx][ny]) {
if(minX == nx) {
if(minY > ny) {
minX = nx;
minY = ny;
}
} else if(minX > nx) {
minX = nx;
minY = ny;
}
}
}
while(true) {
dist = new int[n][n];
minX = Integer.MAX_VALUE;
minY = Integer.MAX_VALUE;
minDist = Integer.MAX_VALUE;
bfs(x,y);
if(minX != Integer.MAX_VALUE && minY != Integer.MAX_VALUE) { // ๋จน์ ์ ์๋ ๋ฌผ๊ณ ๊ธฐ๊ฐ ์กด์ฌํ๋ค๋ฉด
eatCount++; //๋จน์ ํ์ ๋๋ ค์ค
x = minX;
y = minY;
map[x][y] = 0; // ์์น๋ก ์ด๋
time += dist[x][y]; // ๋จ์ด์ ธ ์๋ ๊ฑฐ๋ฆฌ๋ ๊ณง ์๊ฐ
...
} else
break;
}
if(eatCount == babyShark) {
babyShark++;
eatCount = 0;
}
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Queue;
import java.util.LinkedList;
public class Bruteforce_11 {
static int[][] map;
static int[][] dist;
static int[] dx = {0,-1,1,0};
static int[] dy = {-1,0,0,1};
static int n, minX, minY, minDist, babyShark = 2, eatCount = 0, time = 0;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
n = Integer.parseInt(br.readLine());
map = new int[n][n];
int x=0, y=0;
for(int i=0; i<n; i++) {
String[] s = br.readLine().split(" ");
for(int j=0; j<n; j++) {
map[i][j] = Integer.parseInt(s[j]);
if(map[i][j] == 9) {
x = i;
y = j;
map[x][y] = 0;
}
}
}
while(true) {
dist = new int[n][n];
minX = Integer.MAX_VALUE;
minY = Integer.MAX_VALUE;
minDist = Integer.MAX_VALUE;
bfs(x,y);
if(minX != Integer.MAX_VALUE && minY != Integer.MAX_VALUE) {
eatCount++;
x = minX;
y = minY;
map[x][y] = 0;
time += dist[x][y];
if(eatCount == babyShark) {
babyShark++;
eatCount = 0;
}
} else
break;
}
System.out.println(time);
}
static void bfs(int a, int b) {
Queue<Node> q = new LinkedList<>();
q.add(new Node(a,b));
while(!q.isEmpty()) {
Node cur = q.poll();
int x = cur.x;
int y = cur.y;
for(int i=0; i<4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
if(nx < 0 || ny < 0 || nx >= n || ny >= n)
continue;
if(dist[nx][ny] != 0 || map[nx][ny] > babyShark)
continue;
dist[nx][ny] = dist[x][y]+1;
if(map[nx][ny] != 0 && map[nx][ny] < babyShark) {
if(minDist > dist[nx][ny]) {
minDist = dist[nx][ny];
minX = nx;
minY = ny;
} else if(minDist == dist[nx][ny]) {
if(minX == nx) {
if(minY > ny) {
minX = nx;
minY = ny;
}
} else if(minX > nx) {
minX = nx;
minY = ny;
}
}
}
q.add(new Node(nx,ny));
}
}
}
static class Node{
int x;
int y;
Node(int x, int y){
this.x = x;
this.y = y;
}
}
}
์ฑ๊ณตโจ