[백준] 16197 두 동전 - BFS + 아이디어 JAVA

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

16197번: 두 동전

코드설명

BFS 문제입니다.

 

문제에서 이해해야하는점은, 동전이 상하좌우로 했을때 같이 움직인다는 점입니다. 그렇기에 twoCoinPair 객체를 생성해서 따로 작업했습니다.

각 동전을 같이 움직이되, 만약 한 동전이 벽에 부딪친다면 다른 동전만 움직입니다. 

한개로 겹칠 수도 있다는점을 유의합니다.

 

문제로직입니다.

1. boolean[][][][] visited = new boolean[N][M][N][M]; 를 활용하여 두개의 코인이 두개 다 같은 위치에 도달할 경우를 제외시켜서 시간초과를 없애고, 최단거리를 찾을 수 있습니다. 처음에 방문처리를 어떻게 해야할까 고민했었는데 두개의 코인이 하나의 움직임으로 보기에 이런식으로 4차원 배열을 선언해야 각 위치 방문처리가 가능합니다.
2. 첫번째 동전과 두번째 동전을 하나의 동전으로 묶어서 작업해야합니다.
   1. '상하좌우'로 이동했을때 첫번쨰 동전이 만약에 범위 내에서 '#' (벽)을 만난다면 현재 위치 그대로 냅둡니다.(범위조건을 넣어야 ArrayOutOfIndex가 나오지 않습니다.
   2. 각 동전들의 다음 위치를 계산했다면, 이제 각 동전들이 몇개가 나갔는지 세줍니다. (goOutCnt) 
      
      1. 각 동전이 나간 수가 1개라면, 1개만 나갔으니 성공입니다. 이떄는 answer = cnt 하고 종료시킵니다.
      2. 만약 나간 수가 2개라면, 모든 동전이 나갔으므로 실패이므로 아무 작업을 하지 않습니다. (Queue에 넣거나 하지 않습니다.)
      3. 만약 나간수가 아무것도 없다면, 계속해서 Queue를 통해 지속합니다. 이때 이미 위에서 아무동전도 나가지 않았으므로 visited[nr1][nc1][nr2][nc2] 를 해도 ArrayOutOfIndex가 나오지 않습니다. 그리고 한번 움직인것이니 cnt + 1 처리합니다.
3. 10번 움직일경우 실패한것과 마찬가지이므로 -1 을 출력합니다.

BFS를 연습하기 좋은 문제인 것 같습니다.

코드

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 {
	
	public static int N, M;
	public static char[][] board;
	public static int[] dx= {-1,1,0,0};
	public static int[] dy = {0,0,-1,1};
	public static int answer = -1;
	public static Coin firstCoin = null, secondCoin = null;
    public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	
    	N = Integer.parseInt(st.nextToken());
    	M = Integer.parseInt(st.nextToken());
    	
    	board = new char[N][M];
    	for(int i=0;i<N;i++) {
    		st = new StringTokenizer(br.readLine());
    		board[i] = st.nextToken().toCharArray();
    		for(int j=0;j<M;j++) {
    			if(board[i][j] == 'o' && firstCoin == null) {
    				firstCoin = new Coin(i, j);
    			}else if(board[i][j] =='o' && firstCoin != null) {
    				secondCoin = new Coin(i, j);
    			}
    		}
    	}
    	simulate();
    	System.out.println(answer);
    	
    }
    
    public static void simulate() {
    	Queue<twoCoinPair> q = new LinkedList<twoCoinPair>();
    	boolean[][][][] visited = new boolean[N][M][N][M];
    	q.offer(new twoCoinPair(firstCoin.r, firstCoin.c, secondCoin.r, secondCoin.c, 1));
    	visited[firstCoin.r][firstCoin.c][secondCoin.r][secondCoin.c] = true;
    	
    	while(!q.isEmpty()) {
    		twoCoinPair temp =q.poll();
    		int r1 = temp.r1;
    		int c1 = temp.c1;
    		int r2 = temp.r2;
    		int c2 = temp.c2;
    		int cnt = temp.cnt;
    		
    		if(cnt > 10) return ;
    		
    		
    		
    		for(int dir=0;dir<4;dir++) {
    			int nr1 = r1 + dx[dir];
    			int nc1 = c1 + dy[dir];
    			int nr2 = r2 + dx[dir];
    			int nc2 = c2 + dy[dir];
    			
    			//첫번째 Coin 이동체크, 만약 벽이라면 nr1, nc1은 원래 그대로의 temp값을 가집니다.
    			if( nr1 >= 0 && nr1 < N && nc1 >= 0 && nc1 < M && board[nr1][nc1] == '#'){
    				nr1 = r1;
    				nc1 = c1;
    			}
    			//두번째 Coin 이동체크, 만약 벽이라면 nr2, nc2은 원래 그대로의 temp값을 가집니다.
    			if( nr2 >= 0 && nr2 < N && nc2 >= 0 && nc2 < M && board[nr2][nc2] == '#'){
    				nr2 = r2;
    				nc2 = c2;
    			}
    			
    			int goOutCnt = 0;
    			if( nr1 < 0 || nr1 >= N || nc1 < 0 || nc1 >= M) goOutCnt += 1;
    			if( nr2 < 0 || nr2 >= N || nc2 < 0 || nc2 >= M) goOutCnt += 1;

    			if(goOutCnt == 1) {
    				answer = cnt;
    				return ;
    			}
    			else if(goOutCnt == 2) { //모두 다 나간경우 그냥 신경쓰지 않습니다.
    				
    			}
    			else if(goOutCnt == 0) { //아직 아무것도 안나간경우
    				if(visited[nr1][nc1][nr2][nc2] == true ) continue; //밖에서 visited 처리할시 outofarray 가 나옵니다.
    				visited[nr1][nc1][nr2][nc2] = true;
    				q.offer(new twoCoinPair(nr1, nc1, nr2, nc2, cnt + 1));
    			}
    			
    			
    			
    			
    		}
    		
    	}
    	
    }
    
    
}

class twoCoinPair{
	int r1;
	int c1;
	int r2;
	int c2;
	int cnt;
	public twoCoinPair(int r1, int c1, int r2, int c2, int cnt) {
		this.r1 = r1;
		this.c1 = c1;
		this.r2 = r2;
		this.c2 = c2;
		this.cnt = cnt;
	}
}

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