[BOJ 16197] 두 동전 (Java)

BOJ 16197 두 동전

문제풀이

사방탐색을 통해서 최소이동으로 동전 하나만을 떨어뜨리는 문제다. 사방탐색 + 최소이동을 보자마자 BFS를 떠올려야 하지만 '10번 안으로 들어와야한다.'라는 조건을 보고 바로 DFS 탈출조건을 떠올렸다. 그래서 먼저 DFS로 풀이하게 되었다. 완전탐색을 위해서 모든 경우를 파악해야했는데 이 문제는 다음과 같다.

1. 두 동전이 모두 떨어진 경우
2. 한 동전만 떨어진 경우
3. 두 동전이 모두 떨어지지 않은 경우
   3-1. 두 동전이 모두 벽에 부딪힌 경우
   3-2. 한 동전이 벽에 부딪힌 경우
   3-3. 두 동전이 모두 벽에 부딪히지 않은 경우

위 경우들을 고려하여 구현을 하면 된다. 처음에 시간 절약을 위해 방문체크를 수행하였는데 DFS는 최단거리를 보장하지 않기 때문에 더 짧은 거리가 있음에도 불구하고 방문체크를 하게되면 먼저 방문한 경로 때문에 더 짧은 경로를 탐색하지 않게 된다. 따라서 이 문제는 DFS로 풀이할 경우 방문체크를 해서는 안된다.

BFS로 구현하는 경우에도 위의 경우를 모두 포함하게 구현을 하면 되는데자주 사용하던 큐 사이즈를 이용한 시간 증가 방식의 구현은 통과하지 못하여 Node 객체가 자신이 몇 번째 경우인지를 가지고 있게 하였다. 안되는 이유는 아직 모르겠다...

구현코드

• DFS

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	
	static char[][] map;
	static boolean[][][] visited;
	static int[][] dir = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
	static int N, M, ans;
	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());
		
		ans = Integer.MAX_VALUE;
		map = new char[N][M];
		
		int r1, r2, c1, c2;
		r1 = r2 = c1 = c2 = -1;
		for(int i = 0 ; i < N ; ++i) {
			char[] line = br.readLine().toCharArray();
			for(int j = 0 ; j < M ; ++j) {
				map[i][j] = line[j];
				if(map[i][j] == 'o') {
					if(r1 == -1) {
						r1 = i;
						c1 = j;
					} else {
						r2 = i;
						c2 = j;
					}
				}
			}
		}
		
		solve(0, r1, c1, r2, c2);
		
		if(ans == Integer.MAX_VALUE) ans = -1;
		
		System.out.println(ans);
	}
	private static void solve(int depth, int ar, int ac, int br, int bc) {
		if( depth >= ans || depth >= 10) {
			return;
		}
		
		int anr, anc, bnr, bnc;
		boolean adrop, bdrop;
		for(int d = 0 ; d < 4 ; ++d) {
			adrop = bdrop = false;
			// 첫 번째 동전 이동
			anr = ar + dir[d][0];
			anc = ac + dir[d][1];
			// 두 번째 동전 이동
			bnr = br + dir[d][0];
			bnc = bc + dir[d][1];
			
			if(anr >= N || anr < 0 || anc >= M || anc < 0) {
				adrop = true;
			}
			if(bnr >= N || bnr < 0 || bnc >= M || bnc < 0) {
				bdrop = true;
			}
			
			// 둘 다 떨어진 경우 
			if(adrop && bdrop) continue;
			// 하나 떨어진 경우
			if(adrop || bdrop) {
				ans = ans > depth + 1 ? depth + 1 : ans;
				return;
			}
			
			// 다음 위치가 벽이면 움직이지 않는다. 
			if(!adrop && map[anr][anc] == '#') {
				anr = ar;
				anc = ac;
			}
			if(!bdrop && map[bnr][bnc] == '#') {
				bnr = br;
				bnc = bc;
			}
			
			// 두 동전이 겹친 경우
			if ((anr == bnr) && (anc == bnc)) continue;
			
			// 하나도 안 떨어진 경우 
			solve(depth + 1, anr, anc, bnr, bnc);
		}
	}
}

• 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 {

	static class Node {
		int r, c, t;
		
		Node(int r, int c, int t){
			this.r = r;
			this.c = c;
			this.t = t;
		}
	}
	
	static char[][] map;
	static Queue<Node> q;
	static int[][] dir = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
	static int N, M;
	
	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());
		
		map = new char[N][M];
		q = new LinkedList<Node>();
		
		for(int i = 0 ; i < N ; ++i) {
			char[] line = br.readLine().toCharArray();
			for(int j = 0 ; j < M ; ++j) {
				map[i][j] = line[j];
				if(map[i][j] == 'o') {
					q.offer(new Node(i, j, 0));
				}
			}
		}
		
		System.out.println(bfs());
	}

	private static int bfs() {
		while(!q.isEmpty()) {
			Node coin1 = q.poll();
			Node coin2 = q.poll();
			
			if(coin1.t >= 10) return -1;
	
			for(int d = 0 ; d < 4 ; ++d) {
				boolean drop1 = false;
				boolean drop2 = false;
				
				int nr1 = coin1.r + dir[d][0];
				int nc1 = coin1.c + dir[d][1];
				int nr2 = coin2.r + dir[d][0];
				int nc2 = coin2.c + dir[d][1];
				
				// 두 동전의 떨어짐을 체크 
				if(nr1 >= N || nr1 < 0 || nc1 >= M || nc1 < 0) {
					drop1 = true;
				}
				if(nr2 >= N || nr2 < 0 || nc2 >= M || nc2 < 0) {
					drop2 = true;
				}
				
				// 두 동전 모두 떨어진 경우
				if(drop1 && drop2) continue;
				// 한 동전만 떨어진 경우
				if(drop1 || drop2) {
					return coin1.t + 1;
				}
	
				// 두 동전 모두 안떨어진 경우 
				// 동전이 벽을 만난 경우
				if(map[nr1][nc1] == '#' && map[nr2][nc2] == '#') continue;
				
				if(map[nr1][nc1] == '#') {
					nr1 = coin1.r;
					nc1 = coin1.c;
				}
				if(map[nr2][nc2] == '#') {
					nr2 = coin2.r;
					nc2 = coin2.c;
				}
				
				q.offer(new Node(nr1, nc1, coin1.t + 1));
				q.offer(new Node(nr2, nc2, coin1.t + 1));
			}
		}
		return -1;
	}
}