문제
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풀이
이 문제는 DFS 알고리즘을 사용해서 풀 수 있었던 문제이다.
import java.io.*;
public class Main {
static int[] dx = {-1, 1, 0, 0};
static int[] dy = {0, 0, -1, 1};
static int N;
static int M;
static int min = Integer.MAX_VALUE;
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] str = br.readLine().split(" ");
N = Integer.parseInt(str[0]);
M = Integer.parseInt(str[1]);
char[][] map = new char[N][M];
Pair[] coins = new Pair[2];
int index = 0;
for(int i=0; i<N; i++) {
String input = br.readLine();
for(int j=0; j<M; j++) {
map[i][j] = input.charAt(j);
if(map[i][j]=='o') {
coins[index] = new Pair(i, j);
index++;
}
}
}
dfs(map, coins, 0);
if(min>10)
System.out.println(-1);
else
System.out.println(min);
}
public static void dfs(char[][] map, Pair[] coins, int cnt) {
if(cnt>10)
return;
for(int i=0; i<4; i++) {
boolean flag = false;
Pair[] coins_copy = new Pair[2];
coins_copy[0] = coins[0];
coins_copy[1] = coins[1];
char[][] map_copy = new char[N][M];
for(int k=0; k<N; k++) {
for(int j=0; j<M; j++) {
map_copy[k][j] = map[k][j];
}
}
for(int j=0; j<2; j++) {
Pair coin = coins_copy[j];
coins_copy[j] = null;
int nx = coin.x + dx[i];
int ny = coin.y + dy[i];
if(nx>=0 && nx<N && ny>=0 && ny<M) {
if(map_copy[nx][ny]=='#')
coins_copy[j] = new Pair(coin.x, coin.y);
else {
if(map_copy[nx][ny]=='.') {
if(flag) {
map_copy[nx][ny] = 'o';
}
else {
map_copy[coin.x][coin.y] = '.';
map_copy[nx][ny] = 'o';
}
}
else if(map_copy[nx][ny]=='o') {
flag = true;
map_copy[coin.x][coin.y] = '.';
}
coins_copy[j] = new Pair(nx, ny);
}
}
else {
map_copy[coin.x][coin.y] = '.';
}
}
if(coins_copy[0]==null && coins_copy[1]==null) {
min = Math.min(min, 11);
}
else if(coins_copy[0]==null || coins_copy[1]==null) {
//System.out.println(list_copy.get(0).x+" "+list_copy.get(0).y);
min = Math.min(min, cnt+1);
}
else
dfs(map_copy, coins_copy, cnt+1);
}
}
static class Pair {
int x;
int y;
public Pair(int x, int y) {
this.x = x;
this.y = y;
}
}
}
👶🏻Jr. Programmer