[백준 JAVA]16197 두 동전

문제

 

---

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

16197번: 두 동전

 

 

 

풀이방법

---

우선 어느쪽으로 갈지 중복순열을 통해서 구해주었다. 10개를 넘으면 -1을 출력하기 때문에, 10개를 뽑아주었다.

	static void perm(int cnt) {
		if(cnt==10) {
			min=Math.min(min, bfs());
			return;
		}
		
		for(int i=0; i<4; i++) {
			num[cnt]=i;
			perm(cnt+1);
		}
	}

그 후에는 뽑아준 방향들로 움직이면서, 경계 밖으로 나가지 않았는지 확인을 해준다.

나는 방향마다 if문을 써서, 

1. 동전두개가 모두 떨어졌다면 그 경우는 답에 포함되면 안되므로 Integer.MAX_VALUE을 리턴

2. 동전 둘중 하나가 떨어졌다면 그 경우는 min을 세줘야 하므로, counttime을 리턴

3. 첫번째 동전이 범위에 포함되고, 벽이 아니라면 움직이기

4. 두번째 동전이 범위에 포함되고, 벽이 아니라면 움직이기

 

로 동전들을 이동해 주었다. 전체 코드는 다음과 같다.

코드

---

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

public class Main_16197 {

	static char map[][];
	static int num[];
	static int count,M,N;
	static int coin[][];
	static int min=Integer.MAX_VALUE;
	
	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		String s;
		N=Integer.parseInt(st.nextToken());
		M=Integer.parseInt(st.nextToken());
		int c=0;
		map= new char[N][M];
		coin= new int[2][2];
		for(int i=0; i<N; i++) {
			s = br.readLine();
			for(int j=0; j<M; j++) {
				map[i][j]=s.charAt(j);
				if(map[i][j]=='o') {
					coin[c][0]=i;
					coin[c][1]=j;
					c++;
				}
			}
		}
		num=new int[10];
		perm(0);
		if(min==Integer.MAX_VALUE) {
			System.out.println(-1);
		}
		else {
			System.out.println(min);	
		}
		
		
	}
	
	static void perm(int cnt) {
		if(cnt==10) {
//			System.out.println(Arrays.toString(num));
			min=Math.min(min, bfs());
			return;
		}
		
		for(int i=0; i<4; i++) {
			num[cnt]=i;
			perm(cnt+1);
		}
	}
	static int bfs() {
		int fx=coin[0][0];
		int fy=coin[0][1];
		int sx=coin[1][0];
		int sy=coin[1][1];
		
		int counttime=0;
		
		for(int i=0; i<10; i++) {
			counttime++;
			if(num[i]==0) {
				if(fx-1<0 && sx-1<0) {
					return Integer.MAX_VALUE;
				}
				if(fx-1<0 || sx-1<0) {
					return counttime;
				}
				if(fx-1>=0 && map[fx-1][fy]!='#') {
					fx=fx-1;
				}
				if(sx-1>=0 && map[sx-1][sy]!='#') {
					sx=sx-1;
				}
			}
			if(num[i]==1) {
				if(fy+1>=M && sy+1>=M) {
					return Integer.MAX_VALUE;
				}
				if(fy+1>=M || sy+1>=M) {
					return counttime;
				}
				if(fy+1<M && map[fx][fy+1]!='#') {
					fy=fy+1;
				}
				if(sy+1<M && map[sx][sy+1]!='#') {
					sy=sy+1;
				}
			
			}
			if(num[i]==2) {
				if(fx+1>=N && sx+1>=N) {
					return Integer.MAX_VALUE;
				}
				if(fx+1>=N || sx+1>=N) {
					return counttime;
				}
				if(fx+1<N && map[fx+1][fy]!='#') {
					fx=fx+1;
				}
				if(sx+1<N && map[sx+1][sy]!='#') {
					sx=sx+1;
				}
				
			}
			if(num[i]==3) {
				if(fy-1<0 && sy-1<0) {
					return Integer.MAX_VALUE;
				}
				if(fy-1<0 || sy-1<0) {
					return counttime;
				}
				if(fy-1>=0 && map[fx][fy-1]!='#') {
					fy=fy-1;
				}
				if(sy-1>=0 && map[sx][sy-1]!='#') {
					sy=sy-1;
				}
				
			}
		}
		return Integer.MAX_VALUE;
	}

}