BOJ) 파이프 옮기기 1

파이프 옮기기 1

17070번: 파이프 옮기기 1

풀이

 

옮길 수 있는 모든 경우의 수를 찾는 문제기 때문에 브루트포스 문제다.

직접 다 돌리는데는 BFS나 DFS만큼 편한게 없다고(?) 생각해서 DFS로 풀었다.

문제를 풀면서 막혔던 부분은

 

첫째로, 문제 조건을 잘못 이해했다는 것이다.

파이프의 한쪽 끝을 (N, N)로 이동시키는 방법의 개수 

이 문구에서 N,N을 보지 않고 N,y or x,N으로 이동한 파이프들을 구해줬었다...

 

두번째로는 실수라기 보다는 기둥의 시작점인 (0,0)에서 시작했다는 것이다.

편의상 기둥의 상단과 하단이 있다고 친다면, 처음 기둥의 상단이 0,0 에 하단이 1,0에 존재한다.

여기서 상단을 기준으로 로직을 짰는데, 뭔가가 어긋났는지 잘 안됐다.

그래서 하단인 (1,0)부터 시작을 해주고 조건을 바꿔주었다.

 

위의 두 부분을 신경쓰니까 바로 통과됐다.

dfs를 통해서 기둥이 N,N에 도달하는 지점 (코드에서 n-1,n-1에 도달하는 지점)을 찾아서 답을 구해주었고,

가로,세로,대각선인 경우에 움직일 수 있는 방향을 switch문을 통해 지정해줬다.

 

코드 1

N이 3~16이나 돼서 효율이 좋지 못했다.

하지만, 다른 방법은 딱히 떠오르지 않아서 다르게 풀어보는 것은 포기했다.

 

대신 코드를 조금 더 줄이기 위해 if 문이 여러개 쓰이는 부분을 조금 수정해주었다.

방향에 따라 움직이는 방법을 정해주는 부분은 for문을 통해서 바꿔줬고

움직일 수 있는지 확인하는 canMove 부분의 if문을 줄이기 위해서, 가로 세로로 움직이는 horizon과 vertical 변수를 dx dy로 각 방향마다 다음 좌표로 움직일 수 있도록 설정해줬다.

 

코드 2

효율을 크게 좋지는 않지만, 코드 라인이 줄어든 것에 만족한다.

 

코드 1

 

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

public class Main {
    final static int[] horizon = {1,0}, vertical = {0,1};
    final static int BLANK =0, WALL =1;

    static int answer, n, map[][];

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        map = new int[n][n];

        for(int i=0; i<n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for(int j=0; j<n; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        solution();
        br.close();
    }

    private static void solution() {
        answer =0;
        dfs(new PipePos(1,0,0)); // 끝 부분으로 시작하기
        System.out.println(answer);
    }

    private static void dfs(PipePos pipePos) {
        if(pipePos.x ==n-1 && pipePos.y == n-1) {
            answer++;
            return;
        }
        int dir = pipePos.direction;
        int x = pipePos.x;
        int y = pipePos.y;
        switch (dir) {
            case 0: // 가로, 대각선 가능
                if(canMove(x,y,0)) {
                    dfs(new PipePos(x+horizon[0],y,0));
                }
                if(canMove(x,y,2)) {
                    dfs(new PipePos(x+horizon[0],y+vertical[1],2));
                }
                break;
            case 1: // 세로, 대각선 가능
                if(canMove(x,y,1)) { dfs(new PipePos(x,y+vertical[1],1)); }
                if(canMove(x,y,2)) { dfs(new PipePos(x+horizon[0],y+vertical[1],2)); }
                break;
            case 2: // 가로, 세로, 대각선 가능
                if(canMove(x,y,0)) { dfs(new PipePos(x+horizon[0], y, 0)); }
                if(canMove(x,y,1)) { dfs(new PipePos(x,y+vertical[1],1)); }
                if(canMove(x,y,2)) { dfs(new PipePos(x+horizon[0], y+vertical[1], 2)); }
                break;
            default:
                break;
        }
    }

    private static boolean canMove(int x, int y, int dir) {
        int nextX = x+horizon[0];
        int nextY = y+vertical[1];
        if(dir ==0) { // 가로
            if(nextX >=n) { return false; }
            if(map[y][nextX] == WALL) { return false; }
        } else if(dir ==1) { // 세로
            if(nextY >=n) { return false; }
            if(map[nextY][x] == WALL) { return false; }
        } else { // 대각선
            if (nextX >= n || nextY >= n) { return false; }
            if (map[nextY][nextX] == WALL || map[y][nextX] == WALL || map[nextY][x] == WALL) { return false; }
        }
        return true;
    }
}

class PipePos {
    int x;
    int y;
    int direction;  // 0 : 가로, 1 : 세로, 2 : 대각선

    public PipePos(int x, int y, int direction) {
        this.x =x;
        this.y =y;
        this.direction = direction;
    }
}

 

코드 2

 

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

public class Main {
    final static int[] dx = {1,0,1}, dy = {0,1,1};
    final static int WALL =1;

    static int answer, n, map[][];

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        map = new int[n][n];

        for(int i=0; i<n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for(int j=0; j<n; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        solution();
        br.close();
    }

    private static void solution() {
        answer =0;
        dfs(new PipePos(1,0,0)); // 끝 부분으로 시작하기
        System.out.println(answer);
    }

    private static void dfs(PipePos pipePos) {
        if(pipePos.x ==n-1 && pipePos.y == n-1) {
            answer++;
            return;
        }
        int dir = pipePos.direction;
        int x = pipePos.x;
        int y = pipePos.y;
        switch (dir) {
            case 0: // 가로, 대각선 가능
                for(int i=0; i<3; i++) {
                    if(i != 1) {
                        if(canMove(x,y,i)) { dfs(new PipePos(x+dx[i], y+dy[i], i));}
                    }
                }
                break;
            case 1: // 세로, 대각선 가능
                for(int i=1; i<3; i++) {
                    if(canMove(x,y,i)) { dfs(new PipePos(x+dx[i], y+dy[i], i)); }
                }
                break;
            case 2: // 가로, 세로, 대각선 가능
                for(int i=0; i<3; i++) {
                    if(canMove(x,y,i)) { dfs(new PipePos(x+dx[i], y+dy[i], i));}
                }
                break;
            default:
                break;
        }
    }

    private static boolean canMove(int x, int y, int dir) {
        int nx = x+dx[dir], ny = y+dy[dir];
        if(nx >=n || ny >=n) { return false; }
        if(map[ny][nx] == WALL) { return false; }
        if(dir ==2) {
            if(map[ny][x] == WALL || map[y][nx] == WALL) { return false; }
        }
        return true;
    }
}

class PipePos {
    int x;
    int y;
    int direction;  // 0 : 가로, 1 : 세로, 2 : 대각선

    public PipePos(int x, int y, int direction) {
        this.x =x;
        this.y =y;
        this.direction = direction;
    }
}