[백준] 3197 백조의 호수 - BFS(너비우선탐색) + 유니온파인드(Union Find) JAVA

https://www.acmicpc.net/problem/3197

3197번: 백조의 호수

코드설명

BFS와 유니온파인드 문제입니다.

 

처음에 시간복잡도를 고려하지 않고, 단순히 풀었습니다.

하지만, 단순히 시간복잡도를 고려하지않고 BFS를 활용해 푼다면,

1. 빙판이 물에 의해 녹는 것을 검사하면서 O(R*C)의 시간복잡도

2. 각각의 백조가 연결되어있는지 확인하기 위해 검사하는 O(R*C)의 시간복잡도로

총 O( R*C*R*C )의 시간복잡도가 걸립니다.

 

위의 시간복잡도를 유니온파인드로 대체할경우 O( R*C*m )의 시간복잡도로 변화하기에 통과할 수 있습니다.

 

문제로직입니다.

 

1. 유니온파인드로 물의 부분을 그룹화시키고, 물에 녹을 다음 빙판의 위치를 저장합니다.
2. 첫번째 백조와 두번째 백조가 같은 집합에 속할때까지 계속해서 아래의 로직을 반복합니다.
   1. 물에 녹을 다음 빙판의 위치를 돌면서
      1. 만약 '.'와 'L'를 만날경우 집합을 찾습니다.(unionParent)
      2. 만약 'X'를 만날경우 다음 waterNExtQ에 넣어서 다음 물로 변경시킵니다.

 

문제에서 유의해야할점은, BFS를 진행하면서 바로바로 arr[][] X를 '.'로 변경시키는것이 아닌 해당 로직에서 값에 영향을 주지 않도록 다음 BFS에서 값을 변경시킨다는것입니다. 

또한, waterNextQ를 활용하여 현재 Q에서는 현재 Q에서의 연산만 실행하도록 처리합니다.

이렇게 한턴에서 진행한 연산을 독립적으로 처리하기 위해  각 턴마다 연산한 결과를 waterQ = waterNextQ로 얕은복사시켜주어 이후에 waterQ가 사용하도록 처리합니다.

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
import java.util.regex.Pattern;

public class Main {
	public static int R, C;
	public static char[][] arr;
	public static int answer = 0;
	//상하좌우
	public static int[] dx = {-1,1,0,0};
	public static int[] dy = {0,0,-1,1};
	
	public static int[] parent;
	public static boolean[][] visited;
	public static Node firstSwan = null;
	public static Node secondSwan = null;
	

	//특정 원소가 속한 집합을 찾습니다.
	public static int findParent(int x) {
		// 루트노드가 아니라면, 루트노드를 찾을때까지 재귀적으로 호출 합니다.
		if(x == parent[x]) return x;
		return parent[x] = findParent(parent[x]);
	}
	
	//두 원소가 속한 집합을 합칩니다.
	public static void unionParent(int a, int b) {
		a = findParent(a);
		b = findParent(b);
		if( a < b) parent[b] = a;
		else parent[a] = b;
	}
	
    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];
    	parent = new int[R*C]; // R*C 개의 그룹이 있습니다.
    	visited = new boolean[R][C];
    	for(int i=0;i<R;i++) {
    		String str = br.readLine();
    		for(int j=0;j<C;j++) {
    			arr[i][j] = str.charAt(j);
    			parent[i*C + j] = i*C + j; //Parent를 본인의 인덱스 넘버로 초기화시킵니다.
    			if(arr[i][j] == 'L' && firstSwan == null) {
    				firstSwan = new Node(i, j);
    				arr[i][j] = '.'; // 백조의 위치 또한 물입니다.
    			}else if(arr[i][j] =='L' && secondSwan == null){
    				secondSwan = new Node(i, j);
    				arr[i][j] = '.'; // 백조의 위치 또한 물입니다.
    			}
    			
    		}
    	}
        
    	Queue<Node> waterQ = new LinkedList<>();
    	for(int i=0;i<R;i++) { //처음 시작점에서 물의 위치를 저장하고, 각 그룹들을 나눠주기 위한 작업을 처리합니다.
    		for(int j=0;j<C;j++) {
    			if(arr[i][j] == 'X') continue; //빙판일경우 상관쓰지 않고 넝머갑니다.
    			for(int dir=0;dir<4;dir++) {
    				int nr = i + dx[dir];
    				int nc = j + dy[dir];
    				if(nr < 0 || nr >= R || nc < 0 || nc >= C) continue;
    				if(arr[nr][nc] == '.' || arr[nr][nc] =='L') { //만약 상하좌우에 물이 있을경우 해당 그룹을 맞춰줍니다.
    					unionParent(i * C + j, nr * C + nc);
    				}
    				else if(arr[nr][nc] == 'X' && visited[nr][nc] == false) {
    					waterQ.add(new Node(nr, nc));
    					visited[nr][nc] = true;
    				}
    			}
    		}
    	}
    	
    	
    	while( findParent(firstSwan.r * C + firstSwan.c) != findParent(secondSwan.r * C + secondSwan.c) ) { //첫번째 백조와 두번째
    		
    		visited = new boolean[R][C];
    		Queue<Node> waterNextQ = new LinkedList<>(); //waterNextQ, 다음에 녹을 빙판의 위치입니다.
    		while(!waterQ.isEmpty()) {
    			Node temp = waterQ.poll();
    			int r = temp.r;
    			int c = temp.c;
    			
    			arr[r][c] = '.'; //waterQ는 다음에 녹을 빙판의 위치이게 바로 녹여줍니다. 그래야만, 올바르게 다음 waterQ가 작동합니다. 이렇게하지않을경우 아래의 waternextQ에 올바르게 값이 들어가지 않습니다.
    			for(int dir=0;dir<4;dir++) {
    				int nr = r + dx[dir];
    				int nc = c + dy[dir];
    				if(nr < 0 || nr >= R || nc < 0 || nc >= C) continue;
    				if(arr[nr][nc] == '.' || arr[nr][nc] =='L') { //만약 상하좌우에 물이 있을경우 해당 그룹을 맞춰줍니다.
    					unionParent(r * C + c, nr * C + nc);
    				}
    				else if(arr[nr][nc] == 'X' && visited[nr][nc] == false) {
    					waterNextQ.add(new Node(nr, nc));
    					visited[nr][nc] = true;
    				}
    			}
    		}
    		waterQ = waterNextQ;
    		answer += 1;
    	}
    	
    	System.out.println(answer);
    }
    
}

class Node{
	int r;
	int c;
	public Node(int r, int c) {
		this.r = r;
		this.c = c;
	}
}

 

 

시간초과 나는 코드 ( 유의해야할점은 백조의 위치도 결국 물의 위치로 판단해야하는데 해당사항은 고려하지 않은 코드입니다.)

mport java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
import java.util.regex.Pattern;

public class Main {
	public static int R, C;
	public static String str;
	public static char[][] arr;
	public static int answer = 0;
	//상하좌우
	public static int[] dx = {-1,1,0,0};
	public static int[] dy = {0,0,-1,1};
	public static char[][] newArr;
	public static boolean[][] visited;
	public static Node startL = null;
	public static Node endL = null;
    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 + 2][C + 2];
    	newArr = new char[R+2][C+2];
    	for(int i=1;i<=R;i++) {
    		String str = br.readLine();
    		for(int j=1;j<=C;j++) {
    			arr[i][j] = str.charAt(j-1);
    			if(arr[i][j] == 'L' && startL == null) {
    				startL = new Node(i, j);
    			}else if(arr[i][j] == 'L' && startL != null) {
    				endL = new Node(i, j);
    			}
    		}
    	}
    	
    	simulate();
    	System.out.println();
    }
    
    public static void simulate() {
    	
    	while(true) {
    		answer += 1;
    		for(int i=0;i<R+2;i++) {
    			for(int j=0;j<C+2;j++) {
    				newArr[i][j] = arr[i][j];
    			}
    		}
    		
    		for(int i=1;i<=R;i++) {
    			for(int j=1; j<=C;j++) {
    				
    				if(arr[i][j] == 'X') {
    					
    					for(int dir=0;dir<4;dir++) {
    						int nx = i + dx[dir];
    						int ny = j + dy[dir];
    						if(nx <= 0 || nx > R || ny <= 0 || ny > C) continue;
    						
    						if(arr[nx][ny] == '.') {
    							newArr[i][j] = '.';
    						}
    						
    					}
    				}
    			}
    			
    		}
    		
    		for(int i=0;i<R+2;i++) {
    			for(int j=0;j<C+2;j++) {
    				arr[i][j] = newArr[i][j];
    			}
    		}
    		
    		//한번 연산한뒤 L과 L이 만날 수 있는 방법을 찾기위해서는 L의 위치를 BFs에 너어놓고서 해당 위치를 갈 수 있는지 비교하는것이다.
    		BFS(startL, endL);
    		
    		
    	}
    	
    	
    }
    
    public static void BFS(Node start, Node end) {
    	Queue<Node> q = new LinkedList<>();
    	visited = new boolean[R+2][C+2];
    	visited[start.r][start.c] = true;
    	q.offer(start);
    	while(!q.isEmpty()) {
    		Node temp = q.poll();
    		int r = temp.r;
    		int c = temp.c;
    		if( r == end.r && c == end.c) {
    			System.out.println(answer);
    			System.exit(0);
    			return ;
    		}
    		for(int dir=0;dir<4;dir++) {
    			int nr = r + dx[dir];
    			int nc = c + dy[dir];
    			
    			if(nr < 1 || nr > R || nc < 1 || nc > C) continue;
    			if(visited[nr][nc] == true) continue;
    			
    			if(arr[nr][nc] == '.' || arr[nr][nc] =='L') {
    				visited[nr][nc] = true;
    				q.offer(new Node(nr, nc));
    			}
    			
    		}
    	}
    	
    	
    }
    
    
}

class Node{
	int r;
	int c;
	public Node(int r, int c) {
		this.r = r;
		this.c = c;
	}
}