[백준 3197] 백조의 호수 (JAVA)
문제
풀이
R, C 범위가 1 ≤ R, C ≤ 1500 이기 때문에 단순하게 빙판을 녹일 부분을 찾고 녹인 후 백조끼리 만날 수 있는지 확인하는 방법은 시간초과가 발생합니다.
그래서 녹일 부분을 미리 큐에 저장하고 다음 날에 큐에 들어있는 만큼 녹이고 다시 큐에 저장하는 방식과 백조 또한 이미 방문한 부분은 큐에 넣지 말고 인접한 빙판 부분만 큐에 넣어 두었다가 만날 수 있는지 확인하는 방식을 같이 사용하면 됩니다.
코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main {
static int R, C;
static Loc start, end;
static char[][] lake;
static int[][] dt = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
static boolean[][] visited, swanVisited;
static Queue<Loc> ice = new LinkedList<>();
static Queue<Loc> swan = new LinkedList<>();
static Queue<Loc> temp = new LinkedList<>();
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
R = Integer.parseInt(st.nextToken());
C = Integer.parseInt(st.nextToken());
lake = new char[R][C];
visited = new boolean[R][C];
swanVisited = new boolean[R][C];
for (int i = 0; i < R; i++) {
String s = br.readLine();
for (int j = 0; j < C; j++) {
char c = s.charAt(j);
if (c == 'L') {
if (start == null) start = new Loc(i, j);
else end = new Loc(i, j);
lake[i][j] = '.';
continue;
}
lake[i][j] = c;
}
}
make();
for (int i = 0; i < R; i++) {
for (int j = 0; j < C; j++) {
if (lake[i][j] == '.' && !visited[i][j]) {
make(i, j);
}
}
}
int ans = 1;
while (!meeting()) {
melting();
ans++;
}
System.out.println(ans);
br.close();
}
public static boolean meeting() {
temp.clear();
while (!swan.isEmpty()) {
Loc loc = swan.poll();
if (loc.x == end.x && loc.y == end.y) {
return true;
}
for (int d = 0; d < 4; d++) {
int dx = loc.x + dt[d][0];
int dy = loc.y + dt[d][1];
if (check(dx, dy) && !swanVisited[dx][dy]) {
swanVisited[dx][dy] = true;
if (lake[dx][dy] == '.') {
swan.offer(new Loc(dx, dy));
} else {
temp.offer(new Loc(dx, dy));
}
}
}
}
Queue<Loc> t = swan;
swan = temp;
temp = t;
return false;
}
public static void melting() {
int size = ice.size();
for (int s = 0; s < size; s++) {
Loc loc = ice.poll();
for (int d = 0; d < 4; d++) {
int dx = loc.x + dt[d][0];
int dy = loc.y + dt[d][1];
if (check(dx, dy) && !visited[dx][dy]) {
visited[dx][dy] = true;
lake[dx][dy] = '.';
ice.offer(new Loc(dx, dy));
}
}
}
}
public static void make() {
temp.clear();
temp.offer(new Loc(start.x, start.y));
swanVisited[start.x][start.y] = true;
while (!temp.isEmpty()) {
Loc loc = temp.poll();
for (int d = 0; d < 4; d++) {
int dx = loc.x + dt[d][0];
int dy = loc.y + dt[d][1];
if (check(dx, dy) && !swanVisited[dx][dy]) {
swanVisited[dx][dy] = true;
if (lake[dx][dy] == '.') {
temp.offer(new Loc(dx, dy));
} else {
swan.offer(new Loc(dx, dy));
}
}
}
}
}
public static void make(int x, int y) {
temp.clear();
temp.offer(new Loc(x, y));
visited[x][y] = true;
while (!temp.isEmpty()) {
Loc loc = temp.poll();
for (int d = 0; d < 4; d++) {
int dx = loc.x + dt[d][0];
int dy = loc.y + dt[d][1];
if (check(dx, dy) && !visited[dx][dy]) {
visited[dx][dy] = true;
if (lake[dx][dy] == '.') {
temp.offer(new Loc(dx, dy));
} else {
lake[dx][dy] = '.';
ice.offer(new Loc(dx, dy));
}
}
}
}
}
public static boolean check(int x, int y) {
if (x >= 0 && x < R && y >= 0 && y < C) return true;
return false;
}
public static class Loc {
int x, y;
public Loc(int x, int y) {
this.x = x;
this.y = y;
}
}
}
Author And Source
이 문제에 관하여([백준 3197] 백조의 호수 (JAVA)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@solser12/백준-3197-백조의-호수JAVA저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)