BOJ) 두 동전

두 동전

16197번: 두 동전

풀이

 

블로그에 올리기 창피한 코드지만, 기록을 먼저 해두고 나중에 다시 풀고자 올린다.

브루트 포스를 제대로 사용했다기 보다, 시뮬레이션 문제로 인식하고 풀었기 때문에 메모리와 시간 효율성이 현저히 떨어진다.

 

그래도 로직을 설명하자면, 입력을 받을 때 먼저 두 동전의 위치를 저장했다.

그리고 해당 동전을 step에 따라 돌면서, 10을 초과하면 -1을 출력하고 10 이하에서 동전이 하나 남는 경우는 step을 출력했다.

 

동전을 이동시킬 때는, 범위 안에 있는지 먼저 판단해주었다.

상하좌우로 움직이면서 해당 위치가, map의 범위를 벗어나면 코인이 떨어진다는 의미기 때문이다.

그래서, 범위를 벗어나는 동전이 0개인 경우와 1개인 경우에 따라서 코인을 이동시켰다. 

범위를 벗어나는 동전이 2개인 경우는 의미가 없기 때문에, 따로 저장하지 않았다.

 

범위를 벗어나는 동전이 0개인 경우에는 해당 위치가 벽인지 아닌지만 체크해주었다.

벽이라면 좌표가 움직이지 않도록 설정해서 LinkedList에 넣었다.

 

정말 비효율적이고 메모리가 좋지 않기 때문에, 이 방법을 추천하지 않는다.

나중에 효율적인 코드를 짜내면, 추가하겠습니다.

 

 

코드

 

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

public class DropCoins_16197 {
    private final static int[] dx ={1,0,-1,0}, dy ={0,1,0,-1};
    private final static char COINCH = 'o', WALLCH = '#';

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int y = Integer.parseInt(st.nextToken());
        int x = Integer.parseInt(st.nextToken());
        char[][] map = new char[y][x];
        int[][] coinsPos = new int[2][2];
        int idx =0;

        for(int i=0; i<y; i++) {
            String inputStr = br.readLine();
            for(int j=0; j<x; j++) {
                char ch = inputStr.charAt(j);
                map[i][j] = ch;
                if(ch == COINCH) {
                    coinsPos[idx][0] = j; //x
                    coinsPos[idx++][1] = i; //y
                }
            }
        }

        solution(x,y,map,coinsPos);

        br.close();
    }

    private static void solution(int x, int y, char[][] map, int[][] coinsPos) {
        LinkedList<CoinInfo> moveList = new LinkedList<>();
        moveList.offer(new CoinInfo(coinsPos,0,2));

        while (!moveList.isEmpty()) {
            CoinInfo coins = moveList.poll();

            int step = coins.step;
            if(step >10) {
                System.out.println(-1);
                break;
            }
            if(coins.remains ==1) {
                System.out.println(step);
                break;
            }

            step++;

            if(coins.remains ==2) {
                for(int i=0; i<4; i++) {
                    int x1 = coins.coins[0][0] + dx[i];
                    int y1 = coins.coins[0][1] + dy[i];
                    int x2 = coins.coins[1][0] + dx[i];
                    int y2 = coins.coins[1][1] + dy[i];

                    if(isInArea(x1,y1,x,y) && isInArea(x2,y2,x,y)) {    // 둘 다 범위 안에 있으면
                        if(map[y1][x1] == WALLCH) { // 벽이면 이동 못함
                            y1 -= dy[i];
                            x1 -= dx[i];
                        }
                        if(map[y2][x2] == WALLCH) { // 벽이면 이동 못함
                            y2 -= dy[i];
                            x2 -= dx[i];
                        }
                        moveList.offer(new CoinInfo(new int[][] {{x1,y1},{x2,y2}}, step, 2));
                    } else if(isInArea(x1,y1,x,y) || isInArea(x2,y2,x,y)) { // 하나만 나가는 상황
                        moveList.offer(new CoinInfo(new int[2][2],step,1));
                    } // 둘 다 나가는 상황은 체크 안함
                }
            }
        }
    }

    private static boolean isInArea(int x, int y, int maxX, int maxY) {
        return x >=0 && x<maxX && y>=0 && y<maxY ? true : false;
    }
}

class CoinInfo {
    int[][] coins;
    int step;
    int remains;

    public CoinInfo(int[][] coins, int step, int remains) {
        this.coins = coins;
        this.step = step;
        this.remains = remains;
    }
}