[백준 - 16197][GOLD 4][해설 X] - 두 동전 (JAVA)

문제 링크

---

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

 

문제

---

N×M 크기의 보드와 4개의 버튼으로 이루어진 게임이 있다. 보드는 1×1크기의 정사각형 칸으로 나누어져 있고, 각각의 칸은 비어있거나, 벽이다. 두 개의 빈 칸에는 동전이 하나씩 놓여져 있고, 두 동전의 위치는 다르다.

버튼은 "왼쪽", "오른쪽", "위", "아래"와 같이 4가지가 있다. 버튼을 누르면 두 동전이 버튼에 쓰여 있는 방향으로 동시에 이동하게 된다.

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

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

 

입력

---

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

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

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

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

 

출력

---

첫째 줄에 두 동전 중 하나만 보드에서 떨어뜨리기 위해 눌러야 하는 버튼의 최소 횟수를 출력한다. 만약, 두 동전을 떨어뜨릴 수 없거나, 버튼을 10번보다 많이 눌러야 한다면, -1을 출력한다.

 

해결 코드

---

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());

		char[][] map = new char[N][M];
		Coin[] coins = new Coin[2];
		int idx = 0;

		for (int i = 0; i < N; i++) {
			String input = br.readLine();

			for (int j = 0; j < input.length(); j++) {
				map[i][j] = input.charAt(j);

				if (map[i][j] == 'o') {
					coins[idx++]  = new Coin(i, j);
					map[i][j] = '.';
				}
			}
		}

		Status start = new Status(coins[0],coins[1],0);

		int count = getMinCount(map,start);
		System.out.println(count);
	}

	public static int getMinCount(char[][]map, Status start){
		Queue<Status> q = new LinkedList<>();
		q.add(start);

		int[] dx = {0,0,-1,1};
		int[] dy = {-1,1,0,0};
		int count = -1;
		boolean[][][][] visited = new boolean[map.length][map[0].length][map.length][map[0].length];
		visited[start.first.row][start.first.col][start.second.row][start.second.col] = true;

		while(!q.isEmpty()){
			Status curr = q.poll();

			if(curr.count >= 10){
				continue;
			}

			for(int i=0;i<dx.length;i++){
				Coin first = new Coin(curr.first.row + dx[i],curr.first.col+ dy[i]);
				boolean firstOut = outOfMap(map,first);

				if(!firstOut && map[first.row][first.col] == '#'){
					first = new Coin(curr.first.row,curr.first.col);
				}

				Coin second = new Coin(curr.second.row + dx[i],curr.second.col+ dy[i]);
				boolean secondOut = outOfMap(map,second);

				if(!secondOut && map[second.row][second.col] == '#'){
					second = new Coin(curr.second.row,curr.second.col);
				}

				if(secondOut && firstOut){
					continue;
				}else if((firstOut && !secondOut) || (!firstOut && secondOut)){
					return curr.count+1;
				}if(visited[first.row][first.col][second.row][second.col]){
					continue;
				}

				visited[first.row][first.col][second.row][second.col] = true;
				q.add(new Status(first,second,curr.count+1));
			}
		}

		return count;
	}

	public static boolean outOfMap(char[][] map, Coin coin){
		return coin.row <0 || coin.row >=map.length || coin.col <0 || coin.col >=map[0].length;
	}
}

class Status{
	Coin first;
	Coin second;
	int count;

	public Status(Coin first, Coin second, int count){
		this.first = first;
		this.second = second;
		this.count = count;
	}
	
}

class Coin{
	int row;
	int col;

	public Coin(int row, int col){
		this.row = row;
		this.col = col;
	}
}

 

실행 결과

---

 

팁

---

• 리턴 값과 조건을 잘 생각하자
• 조건을 따라 방문배열을 만들자