[백준/자바] 16197 두 동전

문제 링크

---

문제

N×M 크기의 보드와 4개의 버튼으로 이루어진 게임이 있다.

보드는 1 ×1 크기의 정사각형 칸으로 나누어져 있고, 각각의 칸은 비어있거나, 벽이다.

두 개의 빈칸에는 동전이 하나씩 놓여 있고, 두 동전의 위치는 다르다.

 

버튼은 "왼쪽", "오른쪽", "위", "아래"와 같이 4가지가 있다.

버튼을 누르면 두 동전이 버튼에 쓰여 있는 방향으로 동시에 이동하게 된다.

 

• 동전이 이동하려는 칸이 벽이면, 동전은 이동하지 않는다.
• 동전이 이동하려는 방향에 칸이 없으면 동전은 보드 바깥으로 떨어진다.
• 그 외의 경우에는 이동하려는 방향으로 한 칸 이동한다. 이동하려는 칸에 동전이 있는 경우에도 한 칸 이동한다.

두 동전 중 하나만 보드에서 떨어뜨리기 위해 버튼을 최소 몇 번 눌러야 하는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 보드의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 20)

둘째 줄부터 N개의 줄에는 보드의 상태가 주어진다.

• o: 동전
• .: 빈 칸
• #: 벽

동전의 개수는 항상 2개이다.

출력

첫째 줄에 두 동전 중 하나만 보드에서 떨어뜨리기 위해 눌러야 하는 버튼의 최소 횟수를 출력한다.

만약, 두 동전을 떨어뜨릴 수 없거나, 버튼을 10번보다 많이 눌러야 한다면, -1을 출력한다.

예제 입력 1

1 2
oo

예제 출력 1

1

예제 입력 2

6 2
.#
.#
.#
o#
o#
##

예제 출력 2

4

예제 입력 3

6 2
..
..
..
o#
o#
##

예제 출력 3

3

예제 입력 4

5 3
###
. o.
###
. o.
###

예제 출력 4

-1

예제 입력 5

5 3
###
.o.
#.#
.o.
###

예제 출력 5

3

---

설명

N×M 크기의 보드를 (N+2) ×(M+2) 크기의 보드로 구성하면 범위에 대한 계산 없이 밖으로 떨어진 경우를 예외 처리할 수 있다.

이동하려는 칸에 동전이 있는 경우에도 한 칸 이동한다. => 동전이 같은 위치에 있어도 된다.

동전이 보드에 직접 입력하면 두 개의 동전이 겹쳤을 때 판단하기 힘들다고 생각해 동전의 위치를 나타내는 클래스를 만들었다.

class coin {
	int x;
	int y;
	
	public coin(int x, int y) {
		this.x = x;
		this.y = y;
	}
}

 

두 동전 중 하나만 보드에서 떨어뜨리기 위해 버튼을 누를 때 생각해야 할 경우는 다음과 같다.

1. 10번 보다 버튼을 많이 눌러야 하는 경우

2. 두 동전이 모두 밖으로 떨어진 경우

3. 두 동전이 모두 보드에 있는 경우 -> 재귀

4. 한 개의 동전만 보드에 있는 경우 -> 결과

 

버튼에 따라 "왼쪽", "오른쪽", "위", "아래" 이동시 다음 변수를 사용한다.

static int dx[] = {-1, 1, 0, 0}; //위 아래 왼쪽 오른쪽
static int dy[] = {0, 0, -1, 1}; //위 아래 왼쪽 오른쪽

이동 변수를 이용해 이동시 다음 조건에 따라 이동한다.

 

• 동전이 이동하려는 칸이 벽이면, 동전은 이동하지 않는다.
• 동전이 이동하려는 방향에 칸이 없으면 동전은 보드 바깥으로 떨어진다.
• 그 외의 경우에는 이동하려는 방향으로 한 칸 이동한다. 이동하려는 칸에 동전이 있는 경우에도 한 칸 이동한다.

for(int i = 0; i < 4; i++) {
			ArrayList<coin> temp = new ArrayList<>();
			for(int j = 0; j < 2; j++) {
				int x = coins.get(j).x + dx[i];
				int y = coins.get(j).y + dy[i];
				
				if(coins.get(j).x < 0) {
					temp.add(new coin(-1, -1));
					break;
				}
				
				if(board[x][y] == '.' || board[x][y] == 'o') {
					temp.add(new coin(x, y));
				}else if(board[x][y] == 'X'){
					temp.add(new coin(-1, -1));
				}else { 
					temp.add(new coin(coins.get(j).x, coins.get(j).y));
				}
			}
			game(count+1, temp);
}

코드