๐ ๋ฌธ์
์์ | ์๋ฏธ |
๊ตฌํ | |
์ฃผ์ํ ์ | |
๊ฒฐ๋ก |
์ฑ์ ๋ ํ๊ต ์์ ๋ก ํฌ๊ธฐ๊ฐ 8×8์ธ ์ฒด์คํ์์ ํ์ถํ๋ ๊ฒ์์ ๋ง๋ค์๋ค. ์ฒด์คํ์ ๋ชจ๋ ์นธ์ ๋น ์นธ ๋๋ ๋ฒฝ ์ค ํ๋์ด๋ค. ์ฑ์ ์ ์บ๋ฆญํฐ๋ ๊ฐ์ฅ ์ผ์ชฝ ์๋ซ ์นธ์ ์๊ณ , ์ด ์บ๋ฆญํฐ๋ ๊ฐ์ฅ ์ค๋ฅธ์ชฝ ์ ์นธ์ผ๋ก ์ด๋ํด์ผ ํ๋ค.
์ด ๊ฒ์์ ํน์ง์ ๋ฒฝ์ด ์์ง์ธ๋ค๋ ์ ์ด๋ค. 1์ด๋ง๋ค ๋ชจ๋ ๋ฒฝ์ด ์๋์ ์๋ ํ์ผ๋ก ํ ์นธ์ฉ ๋ด๋ ค๊ฐ๊ณ , ๊ฐ์ฅ ์๋์ ์์ด์ ์๋์ ํ์ด ์๋ค๋ฉด ๋ฒฝ์ด ์ฌ๋ผ์ง๊ฒ ๋๋ค. ์ฑ์ ์ ์บ๋ฆญํฐ๋ 1์ด์ ์ธ์ ํ ํ ์นธ ๋๋ ๋๊ฐ์ ๋ฐฉํฅ์ผ๋ก ์ธ์ ํ ํ ์นธ์ผ๋ก ์ด๋ํ๊ฑฐ๋, ํ์ฌ ์์น์ ์ ์์ ์ ์๋ค. ์ด๋ํ ๋๋ ๋น ์นธ์ผ๋ก๋ง ์ด๋ํ ์ ์๋ค.
1์ด ๋์ ์ฑ์ ์ ์บ๋ฆญํฐ๊ฐ ๋จผ์ ์ด๋ํ๊ณ , ๊ทธ ๋ค์ ๋ฒฝ์ด ์ด๋ํ๋ค. ๋ฒฝ์ด ์บ๋ฆญํฐ๊ฐ ์๋ ์นธ์ผ๋ก ์ด๋ํ๋ฉด ๋ ์ด์ ์บ๋ฆญํฐ๋ ์ด๋ํ ์ ์๋ค.
์ฑ์ ์ ์บ๋ฆญํฐ๊ฐ ๊ฐ์ฅ ์ค๋ฅธ์ชฝ ์ ์นธ์ผ๋ก ์ด๋ํ ์ ์๋์ง ์๋์ง ๊ตฌํด๋ณด์.
๐ ์ ๋ ฅ
8๊ฐ ์ค์ ๊ฑธ์ณ์ ์ฒด์คํ์ ์ํ๊ฐ ์ฃผ์ด์ง๋ค. '.'์ ๋น ์นธ, '#'๋ ๋ฒฝ์ด๋ค. ๊ฐ์ฅ ์ผ์ชฝ ์๋ซ์นธ์ ํญ์ ๋ฒฝ์ด ์๋๋ค.
๐ ์ถ๋ ฅ
์ฑ์ ์ ์บ๋ฆญํฐ๊ฐ ๊ฐ์ฅ ์ค๋ฅธ์ชฝ ์ ์นธ์ ๋์ฐฉํ ์ ์์ผ๋ฉด 1, ์์ผ๋ฉด 0์ ์ถ๋ ฅํ๋ค.
๐ ์์ ์ ๋ ฅ
๐ ์์ฝ
- ์ฒด์คํ์ ํฌ๊ธฐ๋ 8x8๋ก ์ด๋ฃจ์ด์ ธ์๋ค.
- '.' ์ ๋น์นธ, '#' ์ ๋ฒฝ์ ์๋ฏธํ๋ค.
- 1์ด๋ง๋ค ๋ฒฝ์ ์๋๋ก ๋ด๋ ค์จ๋ค.
- ์ผ๋ฆญํฐ๋ (์ํ์ข์ฐ, ๋๊ฐ์ , ๊ทธ๋๋ก) ์ด๋ํ ์ ์๋ค.
- ์์ง์ด๋ฉด 1์ด๊ฐ ์๋ชจ๋๋ฉฐ, ๋ค์์ผ๋ก ๋ฒฝ์ด ๋ด๋ ค์จ๋ค.
- ์ผ๋ฆญํฐ๋ ์ผ์ชฝ ์๋(7, 0)์ ์์นํ๋ฉฐ, ์ค๋ฅธ์ชฝ ์(0, 7)์ ๋์ฐฉํ ์ ์๋์ง ์์๋ด์ผ ํ๋ค.
๐ ํ์ด
- BFS๋ก ํ๋ฉด ๋๊ฒ ๋ค๊ณ ์๊ฐ์ด ๋ค์๋ค.
- ๊ทธ๋๋ก ๊ตฌํํด๋ ๋๊ฒ ์ง๋ง, 3์ฐจ์ ๋ฐฐ์ด์ ์ด์ฉํด์ n์ด์ ๋ฒฝ์ด ๋ด๋ ค์๋์ง ์ํ๋ฅผ ์ ์ฅํ๋ค.
(์๋ฅผ ๋ค์๋ฉด wall[x][y][k]๋ (x, y)์ k์ด์ ๋ฒฝ์ด ๋ด๋ ค์๋์ง ์ํ๋ฅผ ์ ์ฅํ ์ ์๋ค.) - ๋จผ์ ํ์ ๊ฐ์ฅ ์ผ์ชฝ(7, 0)์ ํ์ฌ ์๊ฐ 0์ด๋ฅผ ๋ฃ๋๋ค.
- ํ๋ฅผ ์ํํ๋ฉด์ ์๊ฐ์ด 8์ด๊ฐ ๋์ด๊ฐ๋ ๊ฒฝ์ฐ๋ ๋์ฐฉ ์ง์ ๊น์ง ์๋ค๋ฉด ๋์ฐฉํ ์ ์๋ค๊ณ ํ๋จํ๋ค.
์๋ํ๋ฉด 8x8 ์ฒดํฌํ์ผ๋ก ์ด๋ฃจ์ด์ ธ ์๊ธฐ ๋๋ฌธ์ ๊ฐ์ฅ ์์ ์๋ ๋ฒฝ๋ 7์ด๋ฉด ๋งจ ์๋๊น์ง ๋์ฐฉ ํ ์ ์๋ค. - ์ด์ ์ ๊ทธ๋๋ก ์์ง์์ ๊ฒฝ์ฐ๋ฅผ ์ํด, k์ด์ ๋ฒฝ์ด ์กด์ฌํ๋ฉด ๋ค๋ฅธ ๋ฐฉํฅ์ ํ์ธํ์ง ์๋๋ก ๊ตฌํํ๋ค.
- ์ดํ๋ก๋ (์ํ์ข์ฐ, ๋๊ฐ์ , ๊ทธ๋๋ก) ์์ง์ด๋ฉด์ ๋ฒ์๊ฐ ๋์ด๊ฐ๋์ง ์ฒดํฌํ๊ณ , k์ด์ ๋ฒฝ์ด ์กด์ฌํ๋์ง ํ์ธํ๋ค.
- ์กฐ๊ฑด์ ๋ง์ผ๋ฉด ํ์ฌ ์๊ฐ + 1์ ํด์ ํ์ ๋ฃ๋๋ค.
๐ ์ฝ๋
import java.util.LinkedList;
import java.util.Queue;
public class BOJ16954 {
int[] dx = {0, -1, 0, 1, 1, -1, 1, -1};
int[] dy = {1, 0, -1, 0, 1, -1, -1, 1};
public int solution(char[][] board) {
int max = 8;
boolean[][][] wall = init(board, max);
Queue<Person> q = new LinkedList<>();
q.offer(new Person(7, 0, 0)); //์ผ์ชฝ ์๋์์ ์ถ๋ฐ
while (!q.isEmpty()) {
Person cur = q.poll();
if (cur.time >= max || cur.x == 0 && cur.y == 7) return 1; //8์ด ์ด์์ด๊ฑฐ๋ ์ค๋ฅธ์ชฝ ์๋ก ๋์ฐฉํ๋ฉด ๊ฐ๋ฅํ ๊ฒ์ผ๋ก ํ๋จ
if (wall[cur.x][cur.y][cur.time]) continue; //ํด๋น ์๊ฐ์ ๋ฒฝ์ด ์กด์ฌํ๋ฉด ๋ค๋ฅธ ๋ฐฉํฅ์ ํ์ธํ์ง ์๋๋ค.
for (int i = 0; i < max; i++) { //์ํ์ข์ฐ, ๋๊ฐ์ ํ์ธ
int nx = cur.x + dx[i];
int ny = cur.y + dy[i];
if (nx < 0 || ny < 0 || nx >= max || ny >= max) continue; //๋ฒ์ ๋ฒ์ด๋๋์ง ํ์ธํ๊ธฐ
if (wall[nx][ny][cur.time]) continue; //ํด๋น ์๊ฐ์ ๋ฒฝ์ด ์กด์ฌํ๋ ํ์ธ
q.offer(new Person(nx, ny, cur.time + 1));
}
q.offer(new Person(cur.x, cur.y, cur.time + 1)); //์๊ฐ์ ๋๋ฆฌ๊ณ , ์์ง์ด์ง ์๋ ๊ฒฝ์ฐ ํ์ ๋ฃ๊ธฐ
}
return 0;
}
private boolean[][][] init(char[][] board, int max) {
boolean[][][] result = new boolean[max][max][max];
for (int i = 0; i < max; i++) {
for (int j = 0; j < max; j++) {
if (board[i][j] == '#') { //๋งจ ์๋๊น์ง ๋ฒฝ์ ์ด๋ํ์ฌ ์๊ฐ์ ์ฒดํฌํ๋ค.
int time = 0;
for (int k = i; k < max; k++) {
result[k][j][time++] = true;
}
}
}
}
return result;
}
static class Person {
int x, y, time; //x,y ์ขํ์ ํ์ฌ ์๊ฐ
public Person(int x, int y, int time) {
this.x = x;
this.y = y;
this.time = time;
}
}
}
16954๋ฒ: ์์ง์ด๋ ๋ฏธ๋ก ํ์ถ
์ฑ์ ๋ ํ๊ต ์์ ๋ก ํฌ๊ธฐ๊ฐ 8×8์ธ ์ฒด์คํ์์ ํ์ถํ๋ ๊ฒ์์ ๋ง๋ค์๋ค. ์ฒด์คํ์ ๋ชจ๋ ์นธ์ ๋น ์นธ ๋๋ ๋ฒฝ ์ค ํ๋์ด๋ค. ์ฑ์ ์ ์บ๋ฆญํฐ๋ ๊ฐ์ฅ ์ผ์ชฝ ์๋ซ ์นธ์ ์๊ณ , ์ด ์บ๋ฆญํฐ๋ ๊ฐ์ฅ ์ค๋ฅธ์ชฝ
www.acmicpc.net
'Algorithm' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
๐ค BOJ16954 ์์ง์ด๋ ๋ฏธ๋ก ํ์ถ (Java) (0) | 2021.03.08 |
---|---|
๐ 2019 ์นด์นด์ค ๋ธ๋ผ์ธ๋ ๊ณต์ฑ: ํ๋ณดํค (Java) (0) | 2020.05.03 |
๐ค 2020 ์นด์นด์ค ๋ธ๋ผ์ธ๋ ๊ณต์ฑ: ์๋ฌผ์ ์ ์ด์ (Java) (0) | 2020.04.28 |
๐ ํ๋ก๊ทธ๋๋จธ์ค: Lv3. ์ ๊ตญ ์ฌ์ฌ (Java) (0) | 2020.04.25 |
๐ ์นด์นด์ค 2019 ๊ฒจ์ธ ์ธํด์ญ: ๋ถ๋ ์ฌ์ฉ์(Lv3) (0) | 2020.04.05 |
๐ ์นด์นด์ค 2019 ๊ฒจ์ธ ์ธํด์ญ: ํฌ๋ ์ธ ์ธํ๋ฝ๊ธฐ ๊ฒ์(Lv2) (0) | 2020.04.01 |