https://doj.kr/ko/problems/663
아이디어
격자 그리드 BFS 문제의 6개의 버전을 총집해놓은 문제다. 공통적으로 아래의 코드베이스를 사용하겠다.
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main {
static BufferedReader rd = new BufferedReader(new InputStreamReader(System.in));
static StringTokenizer tk;
static int[] dy = {-1, 1, 0, 0};
static int[] dx = {0, 0, -1, 1};
static int N, M, T;
static int sy, sx, ey, ex;
static char[][] graph;
public static void main(String[] args) throws Exception {
tk = new StringTokenizer(rd.readLine());
N = Integer.parseInt(tk.nextToken());
M = Integer.parseInt(tk.nextToken());
T = Integer.parseInt(tk.nextToken());
graph = new char[N][];
for (int y=0; y<N; y++) {
graph[y] = rd.readLine().toCharArray();
}
for (int y=0; y<N; y++) {
for (int x=0; x<M; x++) {
char ch = graph[y][x];
if (ch == 'S') {
sy = y;
sx = x;
}
else if (ch == 'E') {
ey = y;
ex = x;
}
}
}
System.out.println(/* character name */);
System.out.println(/* solveXXX() */);
}
static class Cell {
int y, x;
Cell(int y, int x) {
this.y = y;
this.x = x;
}
}
static boolean out(int y, int x) {
return (y < 0 || y >= N || x < 0 || x >= M);
}
// define "int solveXXX()"...
}Miria
- 설명 그대로 감시 구역을 적용해 최단 경로를 찾고, 없으면 아예 무시하면서 한번 더 최단 경로를 찾으면 된다.
static int solveMiria() {
Queue<Cell> q = new ArrayDeque<>();
boolean[][] enqueued = new boolean[N][M];
q.add(new Cell(sy, sx));
enqueued[sy][sx] = true;
for (int time = 0; ; time++) {
int size = q.size();
if (size == 0)
break; // not return -1
for (int j=0; j<size; j++) {
Cell cell = q.poll();
int y = cell.y;
int x = cell.x;
if (y == ey && x == ex) {
return time;
}
if (graph[y][x] == '!' && time >= T)
continue;
for (int d=0; d<4; d++) {
int ny = y + dy[d];
int nx = x + dx[d];
if (out(ny, nx) || enqueued[ny][nx])
continue;
if (graph[ny][nx] == '#' || graph[ny][nx] == 'x')
continue;
q.add(new Cell(ny, nx));
enqueued[ny][nx] = true;
}
}
}
for (int y=0; y<N; y++)
for (int x=0; x<M; x++)
enqueued[y][x] = false;
q.add(new Cell(sy, sx));
enqueued[sy][sx] = true;
for (int time = 0; ; time++) {
int size = q.size();
if (size == 0)
return -1;
for (int j=0; j<size; j++) {
Cell cell = q.poll();
int y = cell.y;
int x = cell.x;
if (y == ey && x == ex) {
return time;
}
for (int d=0; d<4; d++) {
int ny = y + dy[d];
int nx = x + dx[d];
if (out(ny, nx) || enqueued[ny][nx])
continue;
if (graph[ny][nx] == '#' || graph[ny][nx] == 'x')
continue;
q.add(new Cell(ny, nx));
enqueued[ny][nx] = true;
}
}
}
}Alisa
- 아이디어는 가장 쉽지만, 구현량은 제일 많은 캐릭터이다. 감시 구역을 생각 안 해도 되는게 장점이다.
- 안전한 칸(
S,E,.)이면서 호수(#)에 인접한 칸인 '호숫가'로부터 5칸이니, 모든 호수 칸부터 시작해 안전한 칸을 따라 6칸 이내의 모든 칸에 Alisa가 갈 수 있는 칸을 표시해놓자. (alisa[][]) - 이제 다시 시간(깊이)을 세면서
alisa칸만 밟으며S부터E까지 BFS로 탐색하면 된다.
static int solveAlisa() {
boolean[][] safe = new boolean[N][M];
for (int y=0; y<N; y++) {
for (int x=0; x<M; x++) {
char ch = graph[y][x];
safe[y][x] = (ch == 'S' || ch == 'E' || ch == '.');
}
}
boolean[][] alisa = new boolean[N][M];
Queue<Cell> q = new ArrayDeque<>();
boolean[][] enqueued = new boolean[N][M];
for (int y=0; y<N; y++) {
for (int x=0; x<M; x++) {
if (graph[y][x] == '#') {
q.add(new Cell(y, x));
enqueued[y][x] = true;
}
}
}
for (int i=-1; i<=5; i++) {
int size = q.size();
for (int j=0; j<size; j++) {
Cell cell = q.poll();
int y = cell.y;
int x = cell.x;
if (i != -1) // not lake
alisa[y][x] = true;
if (i == 5) continue;
for (int d=0; d<4; d++) {
int ny = y + dy[d];
int nx = x + dx[d];
if (out(ny, nx) || enqueued[ny][nx] || (!safe[ny][nx]))
continue;
q.add(new Cell(ny, nx));
enqueued[ny][nx] = true;
}
}
}
q.clear();
for (int y=0; y<N; y++)
for (int x=0; x<M; x++)
enqueued[y][x] = false;
if (alisa[sy][sx]) {
q.add(new Cell(sy, sx));
enqueued[sy][sx] = true;
}
for (int time = 0; ; time++) {
int size = q.size();
if (size == 0)
return -1;
for (int j=0; j<size; j++) {
Cell cell = q.poll();
int y = cell.y;
int x = cell.x;
if (y == ey && x == ex) {
return time;
}
for (int d=0; d<4; d++) {
int ny = y + dy[d];
int nx = x + dx[d];
if (out(ny, nx) || enqueued[ny][nx] || !alisa[ny][nx])
continue;
q.add(new Cell(ny, nx));
enqueued[ny][nx] = true;
}
}
}
}- 메모리: 40.4 MB
- 시간: 68 ms
Sherry
- 벽을 부순 횟수(
c)를 포함한 3차원 좌표를 사용해야 한다. - 다음 노드가 벽(
#)일 때, 현재c가 5보다 작다면c를 1 올려 다음 노드를 추가한다.
static class Cell3 {
int c, y, x;
Cell3(int c, int y, int x) {
this.c = c;
this.y = y;
this.x = x;
}
}
static int solveSherry() {
Queue<Cell3> q = new ArrayDeque<>();
boolean[][][] enqueued = new boolean[6][N][M];
q.add(new Cell3(0, sy, sx));
enqueued[0][sy][sx] = true;
for (int time = 0; ; time++) {
int size = q.size();
if (size == 0)
return -1;
for (int j=0; j<size; j++) {
Cell3 cell = q.poll();
int c = cell.c;
int y = cell.y;
int x = cell.x;
if (y == ey && x == ex) {
return time;
}
if (graph[y][x] == '!' && time >= T)
continue;
for (int d=0; d<4; d++) {
int ny = y + dy[d];
int nx = x + dx[d];
if (out(ny, nx) || enqueued[c][ny][nx])
continue;
if (graph[ny][nx] == '#')
continue;
if (graph[ny][nx] == 'x') {
if (c < 5) {
q.add(new Cell3(c+1, ny, nx));
enqueued[c+1][ny][nx] = true;
}
} else {
q.add(new Cell3(c, ny, nx));
enqueued[c][ny][nx] = true;
}
}
}
}
}- 메모리: 42.0 MB
- 시간: 74 ms
Hanna
- 우선순위 큐(
java.util.PriorityQueue)를 쓴 다익스트라를 사용한다. 더 이상 깊이와 시간이 일치하지 않으므로 시간 정보는 노드에 저장해야 한다. - 이미 다음 방문이 예정되어 있더라도 이후 탐색에서 시간상 더 빠른 길을 찾을지도 모른다. 그러나 그런 케이스가 있다면 최초로 밟은 중복된 칸은 다른 방향에서 올 것이므로, 추가로 같은 칸에 '같은 방향'에서 온 것을 중복(
enqueued)으로 처리한다. 중복 탐색을 막기 위한enqueued배열에 어느 방향에서 왔는지를 추가로 저장해야 하므로 차원을 하나 더 늘린다.
static class Cell3 {
int time, y, x;
Cell3(int time, int y, int x) {
this.time = time;
this.y = y;
this.x = x;
}
}
static int solveHanna() {
Queue<Cell3> q = new PriorityQueue<>(Comparator.comparingInt(cell -> cell.time));
boolean[][][] enqueued = new boolean[4][N][M];
q.add(new Cell3(0, sy, sx));
for (int d=0; d<4; d++)
enqueued[d][sy][sx] = true;
while (!q.isEmpty()) {
Cell3 cell = q.poll();
int time = cell.time;
int y = cell.y;
int x = cell.x;
if (y == ey && x == ex) {
return time;
}
if (graph[y][x] == '!' && time >= T)
continue;
for (int d=0; d<4; d++) {
int ny = y + dy[d];
int nx = x + dx[d];
if (out(ny, nx) || enqueued[d][ny][nx] || graph[ny][nx] == 'x')
continue;
if (graph[y][x] == '#' || graph[ny][nx] == '#') {
q.add(new Cell3(time+5, ny, nx));
} else {
q.add(new Cell3(time+1, ny, nx));
}
enqueued[d][ny][nx] = true;
}
}
return -1;
}- 메모리: 41.5 MB
- 시간: 92 ms
후기
- 지인이 출제한 대회에서 마지막으로 풀게 된 문제다. 캐릭터(풀이법)를 고르는 데 시간을 썼고, 중간에 언어를 바꾸는 일(Python→Java)과 잦은 실수로 대회 중에는 풀지 못했다.
- 대회 중에는 Alisa를 선택했는데, 호숫가=호수+1칸이라는 아이디어를 생각 못하고 안전→호숫가→호수→
alisa까지 돌아갔었다. - 왜 Miria나 Sherry를 안 골랐을까...
유사 개발자