[백준] 16197번 두 동전 - (JAVA)

문제

16197번: 두 동전

※주의※ 실패기록일 뿐 풀이에 대한 설명은 미포함되어 있습니다.

 

---

 

 

고생

나의 풀이는 1시간을 넘겨 실패로 간주하고

정답 코드들을 분석하였다.

나는 인쇄해서 글이나 코드를 읽는걸 좋아한다

일부러 C++로 짠 코드를 골라서

JAVA로 변화시켜 짜면서 내 이해도를 파악했다...

 

---

자바로 재구성한 코드

문제 의도는 BFS라고 한다.

아무래도 최소 거리라서 그건듯하다...

 

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

public class Main {

	static class Node {
		int r, c, t;
		
		Node(int r, int c, int t){
			this.r = r;
			this.c = c;
			this.t = t;
		}
	}
	
	static char[][] map;
	static Queue<Node> q;
	static int[][] dir = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
	static int N, M;
	
	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());
		
		map = new char[N][M];
		q = new LinkedList<Node>();
		
		for(int i = 0 ; i < N ; ++i) {
			char[] line = br.readLine().toCharArray();
			for(int j = 0 ; j < M ; ++j) {
				map[i][j] = line[j];
				if(map[i][j] == 'o') {
					q.offer(new Node(i, j, 0));
				}
			}
		}
		
		System.out.println(bfs());
	}

	private static int bfs() {
		while(!q.isEmpty()) {
			Node coin1 = q.poll();
			Node coin2 = q.poll();
			
			if(coin1.t >= 10) return -1;
	
			for(int d = 0 ; d < 4 ; ++d) {
				boolean drop1 = false;
				boolean drop2 = false;
				
				int nr1 = coin1.r + dir[d][0];
				int nc1 = coin1.c + dir[d][1];
				int nr2 = coin2.r + dir[d][0];
				int nc2 = coin2.c + dir[d][1];
				
				// 두 동전의 떨어짐을 체크 
				if(nr1 >= N || nr1 < 0 || nc1 >= M || nc1 < 0) {
					drop1 = true;
				}
				if(nr2 >= N || nr2 < 0 || nc2 >= M || nc2 < 0) {
					drop2 = true;
				}
				
				// 두 동전 모두 떨어진 경우
				if(drop1 && drop2) continue;
				// 한 동전만 떨어진 경우
				if(drop1 || drop2) {
					return coin1.t + 1;
				}
	
				// 두 동전 모두 안떨어진 경우 
				// 동전이 벽을 만난 경우
				if(map[nr1][nc1] == '#' && map[nr2][nc2] == '#') continue;
				
				if(map[nr1][nc1] == '#') {
					nr1 = coin1.r;
					nc1 = coin1.c;
				}
				if(map[nr2][nc2] == '#') {
					nr2 = coin2.r;
					nc2 = coin2.c;
				}
				
				q.offer(new Node(nr1, nc1, coin1.t + 1));
				q.offer(new Node(nr2, nc2, coin1.t + 1));
			}
		}
		return -1;
	}
}

 

 

 

---

나의 실패코드

 

 

어려웠던 점

: 델타 이동 시 낙하 여부 판단

 

왜 그랬나?

- 중복 방문을 막기위해 방문 여부를 체크했었다.

 - 방문 여부 체크 시, 인덱스가 밖으로 나가는 지 체크했다.

 - 기왕 이럴 거 낙하여부를 판단하면 좋겠다 싶어 낙하 여부를 판단하는 코드를 넣었다.

 

어디서 꼬였나?

 1) 하난 이동 되고 하나는 이동 못 한다고 해도 이동해야하지 않나???

 => 맞다. dx = x, dy =y를 해줬다면 그렇게 할 수 있었을 거다.

 

 2) 동전 1이 방문했다고 동전 2ㅣ도 안 움직여야 하나?

 => 1번 질문처럼 처리해도 되지만, 애초에 방문체크를 하지 않아도 된다. (깊이 11에 종료하기 때문)

 

 

추가로 얻은 꿀팁

입력 받을 때 코인 좌표들을 -1로 설정해놓으면, 따로 flag 변수를 두지 않고

x1이 수정되어 -1이 아니게 되면 x2를 변화하도록 설정하면된다.

coin_y1 = coin_x1 = coin_y2 = coin_x2 = -1;
    
    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            cin >> map[i][j];
            if(map[i][j]=='o'){
                if(coin_y1 == -1){
                    coin_y1 = i; coin_x1 = j;
                } else {
                    coin_y2 = i; coin_x2 = j;
                }
                map[i][j] = '.';
            }
        }
    }

 

실패코드 전문

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

public class Main {
	// 보드 size
	static int N, M;
	// 보드 상황 저장
	static char arr [][];
	// 방문 여부 저장
	static boolean visit1 [][],  visit2 [][];
	// 방향 이동을 위한 x 변화량
	static int[] dirX = {-1, 0, 1, 0};
	// 방향 이동을 위한 y 변화량
	static int[] dirY = {0, -1, 0, 1};
	// 최소값 저장
	static int min = Integer.MAX_VALUE;
	
	
	public static void main(String[] args) throws IOException {
		// 버퍼기반 입력
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		// 구분자를 통한 입력 구분
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		// 세로크기 N 입력
		N = Integer.parseInt(st.nextToken());
		// 가로크기 M 입력
		M = Integer.parseInt(st.nextToken());
		// 보드 사이즈 초기화
		arr = new char [N][M];
		visit1 = new boolean [N][M];
		visit2 = new boolean [N][M];
		
		/// 규칙
		// 동전이 이동 칸이 벽 : 이동X
		// 동전이 이동 방향 칸X : 떨어짐
		// 그 외의 경우 : (해당 칸에 동전이 있어도) 이동하려는 방향으로 한 칸 이동한다.

		// 동전 2개의 위치 임시 저장
		int x1, y1, x2, y2, cnt = 0;
		x1 = y1 = x2 = y2 = 0;
		// 맵 입력
		for (int i = 0; i < N; i++) {
			arr[i] = br.readLine().toCharArray();
			for (int j = 0; j < M; j++) {
				if(arr[i][j] == 'o') {
					if(cnt == 0) {
						x1 = j; y1 = i;
						cnt++;
					}
					if(cnt == 1) {
						x2 = j; y2 = i;
					}
					arr[i][j] = '.';
				}
			}
		}
		System.out.println(y1 + " " + x1 + "  ?  " + y2 + " " + x2);

		dfs(x1, y1, x2, y2, 0);
		
		System.out.println(min);
		
	}
	
	static void dfs(int x1, int y1, int x2, int y2, int cnt) {
		System.out.println(y1 + " " + x1 + "  /  " + y2 + " " + x2 + " : " + cnt);
		// 동전이 겹쳐지면 불가능
		if(x1 == x2 && y1 == y2) {
			System.out.println("나다"); 
			return;
		}
		// 10회 이상이면 포기
		if(cnt > 10) {
			min = Math.min(min, cnt);
			return;
		}
		
		boolean coin1 = false, coin2 = false;
		for (int i = 0; i < 4; i++) {
			int dx1 = x1 + dirX[i], dx2 = x2 + dirX[i];
			int dy1 = y1 + dirY[i], dy2 = y2 + dirY[i];
			
			// 둘 모두 다음 이동이 내부
			if(0<=dx2 && dx2 < M && 0<= dy2 && dy2 < N) {
				if(0<=dx1 && dx1 < M && 0<= dy1 && dy1 < N) {
					coin1 = coin2 = true;
					// 갔던 곳 스킵
					if(visit1[dy1][dx1] || visit2[dy2][dx2] ) continue;
					visit1[dy1][dx1] = visit2[dy2][dx2] = true;
					dfs(dx1, dy1, dx2, dy2, cnt++);
					visit1[dy1][dx1] = visit2[dy2][dx2] = false;
				}
			}
		}
		if(coin1 && !coin2) min = Math.min(min, cnt+1);
		if(!coin1 && coin2) min = Math.min(min, cnt+1);
		
	}
}