백조의 호수
문제
두 마리의 백조가 호수에서 살고 있었다. 그렇지만 두 마리는 호수를 덮고 있는 빙판으로 만나지 못한다.
호수는 행이 R개, 열이 C개인 직사각형 모양이다. 어떤 칸은 얼음으로 덮여있다.
호수는 차례로 녹는데, 매일 물 공간과 접촉한 모든 빙판 공간은 녹는다. 두 개의 공간이 접촉하려면 가로나 세로로 닿아 있는 것만 (대각선은 고려하지 않는다) 생각한다.
아래에는 세 가지 예가 있다.
...XXXXXX..XX.XXX ....XXXX.......XX .....XX..........
....XXXXXXXXX.XXX .....XXXX..X..... ......X..........
...XXXXXXXXXXXX.. ....XXX..XXXX.... .....X.....X.....
..XXXXX..XXXXXX.. ...XXX....XXXX... ....X......XX....
.XXXXXX..XXXXXX.. ..XXXX....XXXX... ...XX......XX....
XXXXXXX...XXXX... ..XXXX.....XX.... ....X............
..XXXXX...XXX.... ....XX.....X..... .................
....XXXXX.XXX.... .....XX....X..... .................
처음 첫째 날 둘째 날
백조는 오직 물 공간에서 세로나 가로로만(대각선은 제외한다) 움직일 수 있다.
며칠이 지나야 백조들이 만날 수 있는 지 계산하는 프로그램을 작성하시오.
=> 백조 두 마리를 만나게 하는 최소 시간 구하기
첫번째 코드 - 시간 초과(2%)
- bfs로 백조가 만나는지 체크
- 0,0 부터 ., L인거 큐에 넣고 다음 얼음 겉면 체크 (치즈 문제와 비슷)
- 1이 true일때까지 반복
우선 0,0부터 계속 반복한다는 거에서 시간 초과 났다고 생각함
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main {
static int R, C;
static char[][] arr;
static List<int[]>list;
static int[] dx = {-1,1,0,0};
static int[] dy = {0,0,1,-1};
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());
arr = new char[R][C];
list = new ArrayList<>();
for(int i = 0; i < R; i++) {
String str = br.readLine();
for(int j = 0; j < C; j++) {
arr[i][j] = str.charAt(j);
if(arr[i][j] == 'L') {
list.add(new int[] {i,j});
}
}
}
int cnt = 0;
while(true) {
if(bfs()) {
break;
}
re();
cnt++;
}
System.out.println(cnt);
}
static void re() {
Queue<int[]> q = new ArrayDeque<>();
boolean[][] visit = new boolean[R][C];
for(int i = 0; i < R; i++) {
for(int j = 0; j < C; j++) {
if(arr[i][j] == '.' && !visit[i][j]) {
q.offer(new int[] {i,j});
visit[i][j] = true;
while(!q.isEmpty()) {
int[] now = q.poll();
for(int k = 0; k < 4; k++) {
int nx = now[0] + dx[k];
int ny = now[1] + dy[k];
if(nx < 0 || ny < 0 || nx >= R || ny >= C || visit[nx][ny]) continue;
if(arr[nx][ny] == '.' || arr[nx][ny] == 'L') {
q.offer(new int[] {nx,ny});
}
else if(arr[nx][ny] == 'X'){
arr[nx][ny] = '.';
}
visit[nx][ny] = true;
}
}
}
}
}
}
static boolean bfs() { // 사람 만나는지 체크
Queue<int[]> q = new ArrayDeque<>();
boolean[][] visit = new boolean[R][C];
q.add(list.get(0));
visit[list.get(0)[0]][list.get(0)[1]] = true;
while(!q.isEmpty()) {
int[] now = q.poll();
if(now[0] == list.get(1)[0] && now[1] == list.get(1)[1]) {
return true;
}
for(int i = 0; i < 4; i++) {
int nx = now[0] + dx[i];
int ny = now[1] + dy[i];
if(nx < 0 || ny < 0 || nx >= R || ny >= C || arr[nx][ny] == 'X' || visit[nx][ny]) continue;
visit[nx][ny] = true;
q.offer(new int[] {nx,ny});
}
}
return false;
}
}두번째 코드 - 시간 초과(2%)
- 녹일 얼음 큐 두개로 나눔
- 입력 받을때 sq에 얼음 아닌 것 넣기
- bfs로 백조가 만나는지 체크
- sq를 bfs로 돌면서 다음 녹일 부분 q에 넣기
- 3번 체크
- q를 bfs로 돌면서 다음 녹일 부분 sq에 넣기
- 3~6 반복
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main {
static int R, C;
static char[][] arr;
static List<int[]> list;
static int[] dx = { -1, 1, 0, 0 };
static int[] dy = { 0, 0, 1, -1 };
static Queue<int[]> sq = new ArrayDeque<>();
static Queue<int[]> q = new ArrayDeque<>();
static boolean[][] visit;
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());
arr = new char[R][C];
list = new ArrayList<>();
for (int i = 0; i < R; i++) {
String str = br.readLine();
for (int j = 0; j < C; j++) {
arr[i][j] = str.charAt(j);
if (arr[i][j] == 'L') {
list.add(new int[] { i, j });
}
if (arr[i][j] != 'X') {
sq.offer(new int[] { i, j });
}
}
}
int cnt = 0;
while (true) {
if (bfs()) {
break;
}
re();
cnt++;
if(bfs()){
break;
}
re2();
cnt++;
}
System.out.println(cnt);
}
static void re() {
visit = new boolean[R][C];
while (!sq.isEmpty()) {
int[] now = sq.poll();
for (int k = 0; k < 4; k++) {
int nx = now[0] + dx[k];
int ny = now[1] + dy[k];
if (nx < 0 || ny < 0 || nx >= R || ny >= C || visit[nx][ny])
continue;
if (arr[nx][ny] == 'X') {
arr[nx][ny] = '.';
q.offer(new int[] { nx, ny });
}
visit[nx][ny] = true;
}
}
}
static void re2() {
visit = new boolean[R][C];
while (!q.isEmpty()) {
int[] now = q.poll();
for (int k = 0; k < 4; k++) {
int nx = now[0] + dx[k];
int ny = now[1] + dy[k];
if (nx < 0 || ny < 0 || nx >= R || ny >= C || visit[nx][ny])
continue;
if (arr[nx][ny] == 'X') {
arr[nx][ny] = '.';
sq.offer(new int[] { nx, ny });
}
visit[nx][ny] = true;
}
}
}
static boolean bfs() { // 사람 만나는지 체크
Queue<int[]> q = new ArrayDeque<>();
boolean[][] visit = new boolean[R][C];
q.add(list.get(0));
visit[list.get(0)[0]][list.get(0)[1]] = true;
while (!q.isEmpty()) {
int[] now = q.poll();
if (now[0] == list.get(1)[0] && now[1] == list.get(1)[1]) {
return true;
}
for (int i = 0; i < 4; i++) {
int nx = now[0] + dx[i];
int ny = now[1] + dy[i];
if (nx < 0 || ny < 0 || nx >= R || ny >= C || arr[nx][ny] == 'X' || visit[nx][ny])
continue;
visit[nx][ny] = true;
q.offer(new int[] { nx, ny });
}
}
return false;
}
}세번째 코드 - 성공
- 백조 체크 할때 → 만약 빙하 부분을 만나면 그 부분을 q에 넣기
- 백조 큐 다 돌고 난 후 → q를 백조 큐에 넣기 (다음 시간에 이 부분부터 돌면 됨)
- 빙하 큐 → 큐 사이즈만큼만 돌기
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main {
static int R, C;
static char[][] arr;
static List<int[]> list;
static int[] dx = { -1, 1, 0, 0 };
static int[] dy = { 0, 0, 1, -1 };
static Queue<int[]> swan_q = new ArrayDeque<>(); // 백조
static boolean[][] swan_visit;
static Queue<int[]> melt_q = new ArrayDeque<>();
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());
arr = new char[R][C];
swan_visit = new boolean[R][C];
list = new ArrayList<>();
for (int i = 0; i < R; i++) {
String str = br.readLine();
for (int j = 0; j < C; j++) {
arr[i][j] = str.charAt(j);
if (arr[i][j] == 'L') {
list.add(new int[] { i, j });
}
if (arr[i][j] != 'X') {
melt_q.offer(new int[] { i, j });
}
}
}
swan_q.offer(new int[]{list.get(0)[0], list.get(0)[1]});
swan_visit[list.get(0)[0]][list.get(0)[1]] = true;
int cnt = 0;
while (!meet()) {
melt();
cnt++;
}
System.out.println(cnt);
}
static void melt() {
int size = melt_q.size();
for(int i = 0; i < size; i++){
int[] now = melt_q.poll();
for(int k = 0; k < 4; k++){
int nx = now[0] + dx[k];
int ny = now[1] + dy[k];
if (nx < 0 || ny < 0 || nx >= R || ny >= C)
continue;
if(arr[nx][ny] == 'X'){
arr[nx][ny] = '.';
melt_q.offer(new int[]{nx,ny});
}
}
}
}
static boolean meet() { // 사람 만나는지 체크
Queue<int[]> q = new ArrayDeque<>();
while (!swan_q.isEmpty()) {
int[] now = swan_q.poll();
if (now[0] == list.get(1)[0] && now[1] == list.get(1)[1]) {
return true;
}
for (int i = 0; i < 4; i++) {
int nx = now[0] + dx[i];
int ny = now[1] + dy[i];
if (nx < 0 || ny < 0 || nx >= R || ny >= C || swan_visit[nx][ny])
continue;
swan_visit[nx][ny] = true;
if(arr[nx][ny] == 'X'){
q.offer(new int[] { nx, ny });
}
else{
swan_q.offer(new int[] { nx, ny });
}
}
}
swan_q = q;
return false;
}
}
기록하자