[Java] 15684번 사다리 조작

1. 문제 링크 및 문제

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

1-1 문제 요약

:N*M 크기의 맵, 가로선을 추가하여 i번 세로선의 결과가 i번으로 나와야 함.
이 때 추가해야 하는 가로선 개수의 최솟값(최대 3개)

2. 해결 방법 생각해보자 ...

1. i번 세로선의 결과가 i번으로 나오는 코드 작성 T/F
2. False 일 때 사다리(가로선) 1개 추가 생성
   조건. 가로선이 연속하지 않게 작성
3. 가로선 추가한 맵으로 1, 2 반복.
   가로선이 3개일 때도 1번이 F 이면 -1

3. 내 코드

import java.util.*;
import java.io.*;

public class Main {

    static int N,M,H;
    static int[][] map;
    static int MinResult = 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 = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        H = Integer.parseInt(st.nextToken());

        map = new int[H][N];

        for(int i=0;i<M;i++){
            st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            map[x-1][y-1] = 1;
        }
		// <-- 
        
        MakeLadder(0);
        if(MinResult > 3 ){
            System.out.println(-1);
        }else{
            System.out.println(MinResult);
        }
    }

	// 사다리 생성하기	
    public static void MakeLadder(int count){

        if(CheckLadder(map)){
            MinResult = Math.min(MinResult, count);
            return;
        }

        if(count==3) return;
        
        for(int i=0;i<H;i++){
            for(int j=0;j<N-1;j++){
                if(map[i][j] == 0){
                    if(j>0 && map[i][j-1] == 1) continue;
                    if(j<N-2 && map[i][j+1] == 1)continue;
                    map[i][j] = 1;
                    MakeLadder(count+1);
                    map[i][j] = 0;

                }
            }
        }

    }

	// i번 사다리가 i번으로 나오는 지 확인
    public static boolean CheckLadder(int[][] NewMap){
        for(int i=0;i<N;i++){
            int now = i;
            for(int j=0;j<H;j++){
                if(map[j][now] == 1 ){
                    now += 1;
                }else if( now > 0 && map[j][now-1] == 1){
                    now -= 1;
                }
            }
            if(i != now) return false;
        }

        return true;
    }
}

이것도 맞기는 하지만, 시간 오래걸림.

4. 참고하여 최적화한 코드

import java.util.*;
import java.io.*;

public class Main {

    static int N,M,H;
    static int[][] map;
    static int MinResult;
    static boolean finish = false;

    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];

        for(int i=0;i<M;i++){
            st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            map[x][y] = 1;
            map[x][y+1] = 2;
        }

        for(int i=0;i<=3;i++){
            MinResult = i;
            MakeLadder(1,0);
            if(finish)break;
        }
        System.out.println((finish)? MinResult:-1);

    }

    public static void MakeLadder(int x, int count){
        if(finish)return;
        if(MinResult == count){
            if(CheckLadder(map)) finish = true;
            return;
        }
        
        for(int i=x;i<H+1;i++){
            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;
                    MakeLadder(i,count+1);
                    map[i][j] = map[i][j+1] = 0;

                }
            }
        }
    }

    public static boolean CheckLadder(int[][] NewMap){
        for(int i=1;i<N;i++){
            int x=1, now = i;
            for(int j=0;j<H;j++){
                if(map[x][now] == 1 )now += 1;
                else if( map[x][now] == 2)now -= 1;
                x++;
            }
            if(i != now) return false;
        }

        return true;
    }
}

참고

https://leveloper.tistory.com/96
넘나 대단하십니다... 오늘도 배웠당