[BOJ_17070] 파이프 옮기기 1

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

17070번: 파이프 옮기기 1

골드 5

 

접근 방법 1 :

 

처음 생각 난 dfs로 풀어보았다. 파이프가 놓인 방향이 가로면 0, 대각선이면 1, 세로면 2로 방향을 정한 후, 각 방향마다 조건을 따져서 위치를 일일이 옮겨주었다. 파이프의 끝부분이 (N-1, N-1)이 될 때까지 계속 진행하도록 하였다.

 

N의 범위가 작아서 시간 초과가 나오지는 않았지만, 21일 java 기준 1724/1801등으로 다른 사람들에 비해 시간을 많이 쓴 것을 확인할 수 있었다.

private static void gopipe(int[][] pipe, int[][] room) {

    int N = room.length;
    int[] dr = {0,1,1,1,0,1,1};
    int[] dc = {1,1,0,1,1,0,1};
    if(pipe[1][0]==N-1 && pipe[1][1]==N-1) {
        count++;
        return;
    }
    int[][] tmp = new int[2][2];
    tmp[0][0] = pipe[1][0];
    tmp[0][1] = pipe[1][1];
    if(pipe[1][0]==pipe[0][0]) {
        for (int d = 0; d < 2; d++) {
            tmp[1][0] = pipe[1][0]+dr[d];
            tmp[1][1] = pipe[1][1]+dc[d];
            if(tmp[1][0]>=N || tmp[1][1]>=N) continue;
            if(room[tmp[1][0]][tmp[1][1]]==1) {
                continue;
            }
            if(d==1) {
                if(room[pipe[1][0]][pipe[1][1]+1]==1 || room[pipe[1][0]+1][pipe[1][1]]==1) continue;
            }
            gopipe(tmp, room);
        }
    }else {
        if(pipe[1][1]==pipe[0][1]) {
            for (int d = 2; d < 4; d++) {
                tmp[1][0] = pipe[1][0]+dr[d];
                tmp[1][1] = pipe[1][1]+dc[d];
                if(tmp[1][0]>=N || tmp[1][1]>=N) continue;
                if(room[tmp[1][0]][tmp[1][1]]==1) continue;
                if(d==3) {
                    if(room[pipe[1][0]][pipe[1][1]+1]==1 || room[pipe[1][0]+1][pipe[1][1]]==1) continue;
                }
                gopipe(tmp, room);
            }
        }else {
            for (int d = 4; d < 7; d++) {
                tmp[1][0] = pipe[1][0]+dr[d];
                tmp[1][1] = pipe[1][1]+dc[d];
                if(tmp[1][0]>=N || tmp[1][1]>=N) continue;
                if(room[tmp[1][0]][tmp[1][1]]==1) continue;
                if(d==6) {
                    if(room[pipe[1][0]][pipe[1][1]+1]==1 || room[pipe[1][0]+1][pipe[1][1]]==1) continue;
                }
                gopipe(tmp, room);
            }
        }
    }
}

 

여기서 시간을 줄이기 위해 파이프가 차지하는 2칸 중, (N-1, N-1)에 더 가까운 파이프 끝만 넘겨주고, 방향을 가리키는 dr, dc 배열의 크기도 3으로 줄였다. 이를 바탕으로 가로, 대각선, 세로 순서를 맞추어서 이전 방향을 파라미터로 넘겨주도록 하였다.

 

이를 통해 664ms에서 436ms까지 줄일 수 있었다. 하지만 여전히 메모리를 30만KB 가까이 쓰는 비효율적인 코드이다.

private static void gopipe(int[] pipe, int dir, int[][] room) {

    int N = room.length;
    int[] dr = {0,1,1};
    int[] dc = {1,1,0};
    if(pipe[0]==N-1 && pipe[1]==N-1) {
        count++;
        return;
    }
    int[] tmp = new int[2];
    if(dir==0) {
        for (int d = 0; d < 2; d++) {
            tmp[0] = pipe[0]+dr[d];
            tmp[1] = pipe[1]+dc[d];
            if(tmp[0]>=N || tmp[1]>=N) continue;
            if(room[tmp[0]][tmp[1]]==1) {
                continue;
            }
            if(d==1) {
                if(room[pipe[0]][pipe[1]+1]==1 || room[pipe[0]+1][pipe[1]]==1) continue;

            }
            gopipe(tmp, d, room);
        }
    }else if(dir==2) {
            for (int d = 1; d < 3; d++) {
                tmp[0] = pipe[0]+dr[d];
                tmp[1] = pipe[1]+dc[d];
                if(tmp[0]>=N || tmp[1]>=N) continue;
                if(room[tmp[0]][tmp[1]]==1) continue;
                if(d==1) {
                    if(room[pipe[0]][pipe[1]+1]==1 || room[pipe[0]+1][pipe[1]]==1) continue;
                }
                gopipe(tmp, d, room);
            }
    }else {
        for (int d = 0; d < 3; d++) {
            tmp[0] = pipe[0]+dr[d];
            tmp[1] = pipe[1]+dc[d];
            if(tmp[0]>=N || tmp[1]>=N) continue;
            if(room[tmp[0]][tmp[1]]==1) continue;
            if(d==1) {
                if(room[pipe[0]][pipe[1]+1]==1 || room[pipe[0]+1][pipe[1]]==1) continue;
            }
            gopipe(tmp, d, room);
        }
    }

}

 

 

접근 방법 2 : 

 

다이나믹 프로그래밍으로 풀어보기로 하였다. (n, n)에서 (m, m)으로 이동할 수 있는 경우의 가짓수를 구할 때에 이전 칸이 가진 경우의 수를 바탕으로 계산할 수 있기 때문이다.

 

파이프 옮기기 1의 경우 다음과 같이 정의할 수 있다.

(r, c)에 갈 수 있는 경우

1. (r, c-1)에 가로나 대각선으로 놓인 파이프 끝점이 있는 경우
2. (r-1, c)에 세로나 대각선으로 놓인 파이프 끝점이 있는 경우
3. (r-1, c-1)에 파이프 끝점이 있는 경우. 이 때에는 이전에 파이프가 어떻게 놓여있는 방향은 상관없다. 단, (r-1, c)와 (r, c-1) 모두 벽이 아니어야 한다.

 

이를 위해 Map이라는 class를 만들어 class 변수로 hor(horizon, 가로), ver(vertical, 세로), cross(대각선)을 두었다.

아래 코드에서 room[i][j]==49를 검사하는 이유는 처음에 벽 배열을 받을 때 Integer 변환 없이 받아왔기 때문이다.

map[0][1].hor = 1;
for (int j = 2; j < N; j++) {
    for (int i = 0; i < N; i++) {
        if(room[i][j]==49) continue;
        map[i][j].hor += map[i][j-1].cross+map[i][j-1].hor;
        if(i-1<0) continue;
        map[i][j].ver += map[i-1][j].ver + map[i-1][j].cross;
        if(room[i-1][j]==49 || room[i][j-1]==49) continue;
        map[i][j].cross += map[i-1][j-1].cross + map[i-1][j-1].ver + map[i-1][j-1].hor;
    }
}
System.out.println(map[N-1][N-1].cross+map[N-1][N-1].hor+map[N-1][N-1].ver);

 

이를 통해 시간은 76ms, 메모리는 11584KB까지 단축할 수 있었다.

 

Map 클래스를 사용하는 경우 처음에 Map[][] 배열을 돌면서 클래스를 생성해주어야 하기 때문에, 3차원 배열 int[][][] map으로 바꾸어서 해보기도 했는데, 시간과 메모리 모두 큰 차이가 나지 않았다.

벽을 가리키는 1을 Integer로 변환하여 1 그대로 쓰는 것과 변환 없이 49로 사용하는 것 역시 시간과 메모리 모두 큰 차이가 나지 않았다.

 

 

느낀점 : 

 

앞으로 경로를 찾는 경우의 문제를 풀 때에는 "(n, n)에서 (m, m)으로 이동할 수 있는 경우의 가짓수를 구할 때에 이전 칸이 가진 경우의 수를 바탕으로 계산한다"는 걸 바탕으로 먼저 풀이 방법을 생각해보아야겠다. 이번 문제는 골드5이고, 범위가 작아서 괜찮았지만 조금 더 커진다면 dfs는 시간 초과가 나올 것이다.