[CodeTree] 삼성 SW 역량테스트 2015 하반기 2번 문제 - 2개의 사탕

문제 설명

N×M 크기의 상자 안에 빨간색 사탕과 파란색 사탕이 각각 하나씩 들어있습니다. 이 상자 안에는 사탕이 지나가지 못하도록 하는 장애물이 여러 개 있고, 사탕이 밖으로 빠져 나올 수 있는 구멍이 딱 하나 있습니다.

이러한 상황에서 빨간색 사탕을 밖으로 빼내려고 합니다. 사탕을 밖으로 빼기 위해서는 상자를 위, 아래, 왼쪽, 오른쪽 방향으로 기울일 수 있는데, 기울어진 방향으로 사탕은 장애물 혹은 다른 사탕에 부딪히기 전 까지 미끌어지게 되며, 미끄러지는 도중에 상자를 다른 방향으로 기울일 수는 없습니다.

예를 들어 위의 예에서 상자를 아래로 기울이게 되면 다음과 같은 모양이 됩니다.

빨간색 사탕을 밖으로 빼야 하지만, 파란색 사탕이 밖으로 나와서는 안됩니다. 즉, 빨간색 사탕이 나오기 전에 파란색 사탕이 먼저 나오면 안되며, 빨간색 사탕이 나올 때 파란색 사탕이 동시에 나오는 것도 안됩니다.

예를 들어 바로 위의 상황에서 왼쪽으로 상자를 기울이게 되면 빨간색 사탕이 밖으로 나오게 되지만, 그 이후에 파란색 사탕 역시 밖으로 나오게 되므로 잘못된 경우입니다.

가장 처음 주어진 그림에서 빨간색 사탕만 밖으로 빼내기 위해서는 순서대로 오른쪽, 아래 그리고 왼쪽 방향으로 기울이면 됩니다.

 

입력 형식

첫째 줄에는 N과 M이 공백을 사이에 두고 주어집니다.

둘째 줄 부터는 N개의 줄에 걸쳐 각 행의 상태에 해당하는 M개의 문자가 공백 없이 주어집니다. 각 문자는 '.', ‘#', ‘B’, ‘R’, 'O’ 중에 하나이며 각 위치에 빈 칸, 장애물, 파란색 사탕, 빨간색 사탕, 출구가 있음을 의미합니다. 상자의 바깥 부분은 전부 장애물로 막혀있게 주어진다 가정해도 좋습니다.

• 3≤N≤10
• 3≤M≤10

출력 형식

빨간색 사탕을 밖으로 빼내기 위해 기울여야 하는 최소 횟수를 출력합니다. 만약 10번 이내에 빨간색 사탕을 밖으로 빼내는 것이 불가능하다면, −1을 출력합니다.

 

입출력 예제

 

예제1

6 6
######
#.##B#
##R..#
#..#.#
#O...#
######

출력

>> 3

 

예제2

6 6
######
#.##B#
###.R#
#..#.#
#...O#
######

출력

>> 1

---

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

public class Main {
	static int N, M, min = Integer.MAX_VALUE;
	static boolean[][][] visit;
	static char[][] arr;
	static int[][] dir = {{0,1},{0,-1},{1,0},{-1,0}}; // 우 좌 하 상
	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());
	    Candy red = null, blue = null;
	    visit = new boolean[N][M][2];
		arr = new char[N][M];
		for(int i=0; i<N; i++) {
			arr[i] = br.readLine().toCharArray();
			for(int j=0; j<M; j++) {
				if(arr[i][j] == 'R') {
					red = new Candy(i, j);
					arr[i][j] = '.';
				}else if(arr[i][j] == 'B'){
					blue = new Candy(i, j);
					arr[i][j] = '.';
				}
			}
		}
		dfs(red, blue, 0);
		System.out.println(min > 10 ? -1 : min);
	}
	private static void dfs(Candy red, Candy blue, int cnt) {
		if(cnt > 10) {
			return;
		}
		if(arr[blue.x][blue.y] == 'O') {
			return;
		}
		if(arr[red.x][red.y] == 'O') {
			min = Math.min(min, cnt);
			return;
		}
		visit[red.x][red.y][0] = true;
		visit[blue.x][blue.y][1] = true;
		Candy[] candies = null;
		for(int d=0; d<4; d++) {
			candies = roll(red, blue, d);
			if(visit[candies[0].x][candies[0].y][0] && visit[candies[1].x][candies[1].y][1]) continue;
			dfs(candies[0], candies[1], cnt+1);
		}
		visit[red.x][red.y][0] = false;
		visit[blue.x][blue.y][1] = false;
	}
	private static Candy[] roll(Candy red, Candy blue, int d) {
		int[] movedRed = move(red, d);
		int[] movedBlue = move(blue, d);
		int redDist = Math.abs(red.x-movedRed[0]) + Math.abs(red.y-movedRed[1]);
		int blueDist = Math.abs(blue.x-movedBlue[0]) + Math.abs(blue.y-movedBlue[1]);
		if(movedRed[0] == movedBlue[0] && movedRed[1] == movedBlue[1] && arr[movedRed[0]][movedRed[1]]!='O') {
			if(redDist < blueDist) {
				movedBlue[0] -= dir[d][0];
				movedBlue[1] -= dir[d][1];
			}else {
				movedRed[0] -= dir[d][0];
				movedRed[1] -= dir[d][1];
			}
		}
		return new Candy[] {new Candy(movedRed[0], movedRed[1]), new Candy(movedBlue[0], movedBlue[1])};
	}
	private static int[] move(Candy candy, int d) {
		int nx = candy.x;
		int ny = candy.y;
		while(arr[nx+dir[d][0]][ny+dir[d][1]] != '#') {
			nx += dir[d][0];
			ny += dir[d][1];
			if(arr[nx][ny]=='O') break;
		}
		return new int[] {nx, ny};
	}
	static class Candy {
		int x, y;
		public Candy(int x, int y) {
			super();
			this.x = x;
			this.y = y;
		}
	}
}

 

[출처]

https://www.codetree.ai/training-field/frequent-problems/problems/two-candies/description?page=3&pageSize=20

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석