[백준] G4 16197 두 동전 (java)

www.acmicpc.net/problem/16197

16197번: 두 동전

 

풀이

 

1) 맵을 만들때 동전의 좌표를 저장해 둔다.

2) dfs를 돌린다. 파라미터는 동전1의 좌표 (r1,c1) , 동전2의 좌표 (r2,c2) , depth

2-1) 탈출조건1 : depth가 10보다 클때 return

2-2) 탈출조건2 : 두 개의 동전이 동시에 밖으로 나갔을 때 return

2-3) 탈출조건3 : 한 개의 동전만 나갔을 경우. min을 갱신 한 후 return;

3) 재귀 부분

3-1) 4방향의 경우를 모두 구하는데 벽을 만나면 바뀌지 않는다.

3-2) depth를 1씩 증가시키면서 dfs 탐색

4) min이 바꼈으면 min 출력, 안바꼈으면 -1 출력

 

주의사항

 

1) 방문체크 필요없다.

 

package com.baekJoon;

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

public class BJ_G4_16197_두동전 {
	static BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
	static StringTokenizer tokens;
	static int N,M,min=Integer.MAX_VALUE;
	static char map[][];
	public static void main(String[] args) throws NumberFormatException, IOException {
		input = new BufferedReader(new StringReader(src));
		tokens = new StringTokenizer(input.readLine());
		N = Integer.parseInt(tokens.nextToken());
		M = Integer.parseInt(tokens.nextToken());
		map = new char [N][M];
		
		int coin[][] = new int[2][2];
		int cnt = 0;
		for(int r=0; r<N; r++) {
			String line = input.readLine();
			for(int c=0; c<M; c++) {
				map[r][c] = line.charAt(c);
				if(map[r][c] == 'o') {
					coin[cnt][0] = r;
					coin[cnt++][1] = c;
				}
			}
		}
//		for(char x[] : map) {
//			System.out.println(Arrays.toString(x));
//		}
		
//		for(int x[] : coin) {
//			System.out.println(Arrays.toString(x));
//		}
		dfs(coin[0][0],coin[0][1],coin[1][0],coin[1][1],0);
		if(min == Integer.MAX_VALUE) {
			System.out.println(-1);
		}else {
			System.out.println(min);
		}
	}

	private static void dfs(int r1, int c1, int r2, int c2, int depth) {
		// 둘중 하나만 벗어났을 경우
		if(depth > 10) {
			return;
		}
		// 둘이 동시에 벗어나도 리턴
		if((!isIn(r1, c1) && !isIn(r2, c2))) { 
			return;
		}
		if((isIn(r1, c1) && !isIn(r2, c2)) || (!isIn(r1, c1) && isIn(r2, c2))) { 
			if(min > depth) {
				min = depth;
			}
			return;
		}
		for(int d=0; d<4; d++) {
			int nr1 = r1 + dr[d];
			int nc1 = c1 + dc[d];
			int nr2 = r2 + dr[d];
			int nc2 = c2 + dc[d];
			
			if(isIn(nr1, nc1) && map[nr1][nc1] == '#') { // 벽만나면 이동 못함 ㅠㅠ
				nr1 = r1;
				nc1 = c1;
			}
			if(isIn(nr2, nc2) && map[nr2][nc2] == '#') { // 벽만나면 이동 못함 ㅠㅠ
				nr2 = r2;
				nc2 = c2;
			}
			dfs(nr1, nc1, nr2, nc2, depth+1);
			
		}
	}
	
	static int dr[] = {0,0,-1,1};
	static int dc[] = {-1,1,0,0};
	
	static boolean isIn(int r, int c) {
		return (r>=0 && c>=0 && r<N && c<M);
	}

	static String src =
			"5 3\r\n" + 
			"###\r\n" + 
			".o.\r\n" + 
			"###\r\n" + 
			".o.\r\n" + 
			"###";
}

 

 

후기

 

 골드4 문제치고는 수월하게 푼 문제였다. 요즘 탐색, 시뮬레이션을 많이 풀다보니까 확실히 dfs가 늘었다.

dfs가 익숙해진것처럼 dp도 익숙해질 수 있을까..