삼성 SW 역량테스트 백준 사다리조작 15684

1. 삼성 SW 역량테스트 백준 사다리조작 15684문제

1.1. 컴퓨팅적 사고

1. n은 열의 개수, m은 가로선의 추가될 개수, h는 열의 개수입력을 받습니다.
2. 그리고 가로선의 추가될 x,y좌표의 값을 체크를 하여 맵에 넣어주는데 조심해야할 부분이 있습니다. 저 같은경우에는 x,y의 좌표값이 들어왔을때 x,y의 좌표는 1로 놓고 x,y+1의 좌표는 2로 놓았습니다. 이렇게 좌표로 놓은이유는 추후에 모든 가로선들을 놓고나서 모든 사다리들을 위에서부터 순회하는 과정에서 이동을 하기 위함입니다. 즉, x,y의 좌표 1의 경우에는 오른쪽으로 이동을 하게 되고, x,y+1의 좌표 2의 경우에는 왼쪽으로 이동하게 처리하였습니다.
3. n,m,n의 변수를 헷갈려했는데, 다시 한번 문제를 읽고 이해하는 문제가 되었습니다. 시간소요가 많이 된 부분이라 천천히 잘 읽으면서 진행해야겠습니다.
4. map의 행,열의 idx값이 1부터 진행되므로 배열할당을 [h+1][n+1]의 범위만큼 할당하여 진행하였습니다.
5. 사다리 즉, 가로선의 개수는 3개를 넘을 수 없다 라는 조건을 처음에 간과하였습니다. 출력부분에 자세히보면 다리를 놓는것은 3개만 가능하고 그 이상이 될 경우 -1을 출력하라라는 조건을 제대로 확인을 못하였습니다.
6. 가로선을 최대 3개까지만 구할 수 있기때문에 0,1,2,3개를 선택하는 조합의 경우로 생각할 수 있습니다. 따라서 for(0-3의 범위)를 하나씩 순회하면서 선택되는 경우를 구할 수 있습니다.(3C0, 3C1,3C2, 3C3) 의 경우라고 생각을 합니다.
7. 이제 DFS를 수행하여 Basement조건을 수립합니다.
8. 모든 가로선을 놓았을때 종료하는 Basement조건을 수립하고 현재 0~3개의 값을 선택하는 경우로 진행되고 있기 때문에 해당되는 조건은 cnt == len의 범위를 만족할때 사다리를 찾는 로직을 구현하면 됩니다.
9. 모든 가로선을 아직 놓지 못하였을때는 1번행부터 h+1의 길이까지 모든 행 ~ 열을 순회하면서 현재 위치와 다음위치의 값이 0) 즉, (x,y), (x,y+1)의 값이 모두 0일 경우이자 가로선을 놓을 수 있는 경우에 가로선을 넣게 하였습니다. 가로선은 (x,y)는 1, (x,y+1)은 2로 넣어 1일 경우 오른쪽으로 이동, 2일경우 왼쪽으로 이동의 경우로 맵에 값을 갱신시켜나갔습니다.
10. 만약 가로선의 개수가 DFS의 종료조건에 걸렸을 경우에 현재 선택된 가로선을 다시 (x,y = 0), (x,y+1 = 0)으로 값들을 해제시켜주었습니다. 그래야지 다른 경우의 가로선을 탐색할 수 있기때문입니다.
11. 이제 모든 가로선들을 놓고, 사다리를 (1~n) 인덱스부터 순차적으로 진행하면서 해당 사다리를 타고 내려가면서 최종적으로 타고 내려온 열의 값이 현재 시작한 열의 값과 같은지 다른지를 체크합니다. 예를 들면, 1번 세로선에서 시작하여 모든 사다리를 타고나서, 최종적으로 끝의 행에 도달하였을때의 y의 값이 같다면 성공적으로 사다리를 타고 내려와서 사다리를 조작한것으로 볼 수 있습니다.
12. 사다리를 타고 내려오는 과정은 다음과 같습니다.
    1. 현재 map의 값이 1이면 오른쪽으로 이동시킵니다.(my++)
    2. 현재 map의 값이 2이면 왼쪽으로 이동시킵니다.(my—)
    3. 가로, 세로를 모두 움직이고나서 아래로 한칸 내려와서 사다리를 이동시킵니다.(mx++)
    4. 최종적으로 my와 현재 출발하는 j값이 같지 않다면 사다리를 제대로 타고내려와서 속인게 아니므로 false를 리턴합니다.

• 실수한점: 모든 사다리가 세로선 i선에서 i까지 도달하는것이 아니라 하나의 그 개수만 찾으면 되는 문제였습니다. 이 부분에서 조합+DFS+BFS으로 모든 경우를 고민하게 되면서 잘못된 로직을 구현하게 되면서 시간이 소요된 문제였습니다.

1.2. 소스코드

package Samsung.done;

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

public class 사다리조작_15684번 {
    static int n, m, h;
    static int[][] map;
    static int answer;
    static boolean isCheck;
    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());
        h = Integer.parseInt(st.nextToken());
        map = new int[h+1][n+1];
        answer = 0;

        int x,y;
        for(int i=0; i<m; i++){
            st = new StringTokenizer(br.readLine());
            x = Integer.parseInt(st.nextToken());
            y = Integer.parseInt(st.nextToken());
            // 가로선 왼쪽: 1, 오른쪽 2
            map[x][y] = 1;
            map[x][y+1] = 2;
        }
        // 가로선을 최대3개까지만 놓을 수 있기때문에 nCi의 경우를 모두 구해준다.
        for(int i=0; i<= 3; i++){
            // i는 몇개 선택된지 여부
            answer = i;
            // dfs(시작점, 선택된 갯수)
            dfs(1, 0, i);
            if(isCheck) break;
        }
        System.out.println(isCheck ? answer : -1);
    }

    private static void dfs(int x, int cnt, int len) {
        // i번 세로선의 결과가 i번이 나온경우 종료!
        if(isCheck) return;
        if(cnt == len){
            if (arriveAtDestination()) {
                isCheck = true;
            }
            return;
        }
        // 모든 경우에 대해서 가로선 경우를 모두 놓아본다.
        for(int i=x; i<h+1; i++){
            // 가로선 j+1까지 확인을 하기 때문에 n까지만 진행합니다.
            for(int j=1; j<n; j++){
                if(map[i][j] == 0 && map[i][j+1] == 0){
                    // 해당점을 선택하는 경우
                    map[i][j] = 1;
                    map[i][j+1] = 2;
                    dfs(i, cnt+1, len);
                    // 해당점을 선택하지 않는 경우
                    map[i][j] = 0;
                    map[i][j+1] = 0;
                }
            }
        }
    }

    private static boolean arriveAtDestination() {
        // 세로선을 확인하면서 나간다.(열)
        for(int i=1; i<=n; i++){
            // 맨위에서 부터 시작하므로 x = 1, y는 해당 세로선부터 순차적으로 확인하므로 i
            int mx = 1;
            int my = i;
            for(int j=0; j<h; j++){
                if(map[mx][my] == 1){
                    my++;        //열 움직이기 오른쪽으로
                }else if(map[mx][my] == 2){
                    my--;        //열 움직이기 왼쪽으로
                }
                //인접한 값이 존재할 수 없으므로 세로로 밑으로 내려간다.
                mx++;
            }
            // y값이 계속해서 사다리를 타고 내려오다가 결국 자신이 출발한 지점과 같지 않게되면 i번 세로선이 i로 도착한게 된게 아니므로 종료
            if(my != i){
                return false;
            }
        }
        return true;
    }
}