재귀/완전탐색 | 백준 15684번 사다리 조작(JAVA) - 2018 삼성 SW 역량 테스트

15684번: 사다리 조작

문제

사다리 게임은 N개의 세로선과 M개의 가로선으로 이루어져 있다. 인접한 세로선 사이에는 가로선을 놓을 수 있는데, 각각의 세로선마다 가로선을 놓을 수 있는 위치의 개수는 H이고, 모든 세로선이 같은 위치를 갖는다. 아래 그림은 N = 5, H = 6 인 경우의 그림이고, 가로선은 없다.

초록선은 세로선을 나타내고, 초록선과 점선이 교차하는 점은 가로선을 놓을 수 있는 점이다. 가로선은 인접한 두 세로선을 연결해야 한다. 단, 두 가로선이 연속하거나 서로 접하면 안 된다. 또, 가로선은 점선 위에 있어야 한다.

위의 그림에는 가로선이 총 5개 있다. 가로선은 위의 그림과 같이 인접한 두 세로선을 연결해야 하고, 가로선을 놓을 수 있는 위치를 연결해야 한다.

사다리 게임은 각각의 세로선마다 게임을 진행하고, 세로선의 가장 위에서부터 아래 방향으로 내려가야 한다. 이때, 가로선을 만나면 가로선을 이용해 옆 세로선으로 이동한 다음, 이동한 세로선에서 아래 방향으로 이동해야 한다.

위의 그림에서 1번은 3번으로, 2번은 2번으로, 3번은 5번으로, 4번은 1번으로, 5번은 4번으로 도착하게 된다. 아래 두 그림은 1번과 2번이 어떻게 이동했는지 나타내는 그림이다.

사다리에 가로선을 추가해서, 사다리 게임의 결과를 조작하려고 한다. 이때, i번 세로선의 결과가 i번이 나와야 한다. 그렇게 하기 위해서 추가해야 하는 가로선 개수의 최솟값을 구하는 프로그램을 작성하시오.

 

입력

첫째 줄에 세로선의 개수 N, 가로선의 개수 M, 세로선마다 가로선을 놓을 수 있는 위치의 개수 H가 주어진다. (2 ≤ N ≤ 10, 1 ≤ H ≤ 30, 0 ≤ M ≤ (N-1)×H)

둘째 줄부터 M개의 줄에는 가로선의 정보가 한 줄에 하나씩 주어진다.

가로선의 정보는 두 정수 a과 b로 나타낸다. (1 ≤ a ≤ H, 1 ≤ b ≤ N-1) b번 세로선과 b+1번 세로선을 a번 점선 위치에서 연결했다는 의미이다.

가장 위에 있는 점선의 번호는 1번이고, 아래로 내려갈 때마다 1이 증가한다. 세로선은 가장 왼쪽에 있는 것의 번호가 1번이고, 오른쪽으로 갈 때마다 1이 증가한다.

입력으로 주어지는 가로선이 서로 연속하는 경우는 없다.

 

출력

i번 세로선의 결과가 i번이 나오도록 사다리 게임을 조작하려면, 추가해야 하는 가로선 개수의 최솟값을 출력한다. 만약, 정답이 3보다 큰 값이면 -1을 출력한다. 또, 불가능한 경우에도 -1을 출력한다.

 

힌트

 

풀이

가로선 입력받기

for(int i=0; i<M; i++) {
    st = new StringTokenizer(br.readLine());
    a = Integer.parseInt(st.nextToken());
    b = Integer.parseInt(st.nextToken());
    ladder[a-1][b-1] = RIGHT; //왼쪽을 기준으로 오른쪽으로 이동
    ladder[a-1][b] = LEFT; //오른쪽을 기준으로 왼쪽으로 이동
}

사다리(가로선)를 입력받는 코드이다. 사다리를 기준으로 이동할 방향을 기록한다. 왼쪽 세로선에서 사다리를 거치면 오른쪽으로 이동하므로 RIGHT 상수 1로 초기화해주고, 오른쪽 세로선에서 사다리를 거치면 왼쪽으로 이동하므로 LEFT 상수 2로 초기화해준다.

왼쪽 예시에서는 오른쪽과 같이 나타낼 수 있다.

새로운 가로선을 만드면서 최소 개수 탐색

완전 탐색을 진행하는 부분에서 각 배열의 인덱스는 위와 같다. 평소 이차원 배열을 탐색할 때처럼 x, y로 하는 것이 아니고 차례대로 숫자를 부여한다. 행은 숫자를 5로 나누었을 때 몫이고, 열은 숫자를 5로 나누었을 때 나머지이다(위 이미지와 달리 실제 구현에서는 0부터 시작하므로 -1되는 것에 주의). 예를 들어 arr[1][2]은 7인데, 7을 5로 나누면 몫이 1이고 나머지가 2로 원래의 행과 열을 구할 수 있다.

static int solve(int pos, int cnt) {
	 if(cnt == 3 || pos == N*H) {
		 if(check())
			 return cnt;
		 return INF;
	 }
	 int ret = INF;
	 int r = pos / N;
	 int c = pos % N;
	 if(c != N-1 && ladder[r][c] == 0 && ladder[r][c] == 0) { 
		 ladder[r][c] = RIGHT;
		 ladder[r][c+1] = LEFT;
		 ret = Math.min(ret, solve(pos + 2, cnt + 1));
		 ladder[r][c] = ladder[r][c+1] = 0;
	 }
	 ret = Math.min(ret, solve(pos + 1, cnt));
	 return ret;
}

solve 함수에서는 모든 경우의 수를 만드는 완전탐색을 진행한다. pos는 각 배열에 부여한 인덱스 값이고, cnt는 추가한 가로선의 길이이다. ret는 새로운 가로선의 최소 개수로 탐색을 시작하기 전 무한대로 초기화한다. r과 c는 위에서 설명했듯이 열의 길이로 나눈 몫과 나머지를 저장한다.

마지막 가로선이 아니고 가로선을 놓을 수 있는 위치(왼쪽과 오른쪽 모두 1이나 2가 없을 때)일 때 가로선을 새로 만들어주고 재귀를 돌린다. 이때 solve(pos+2, cnt+1)에서 pos에 +2를 하는 이유는 다음 칸에도 가로선이 만들어졌기 때문에 탐색을 진행할 필요가 없기 때문이다.

가로선을 놓을 수 없는 위치라면 위치값(pos)만 하나 증가시켜주고 탐색을 진행한다.

만약 새로 놓은 가로선의 개수가 3을 넘어가거나 배열의 끝까지 탐색했다면, 가로선이 제대로 놓였는지 확인한다(check 함수).

 

i번에서 출발하여 i번으로 도착하는지 확인

static boolean check() {
	for(int i=0; i<N; i++) {
		int r = 0;
		int c = i;
		do {
			if(ladder[r][c] == LEFT)
				c --;
			else if(ladder[r][c] == RIGHT)
				c ++;
			r ++;
		} while(r != H);
		
		if(c != i) return false;
	}
	return true;
}

처음 시작할 때는 항상 가로는 0, 세로는 i이다. 가로선이 저장된 배열을 따라 움직인 뒤 가로가 H와 같아진다면 while문을 종료한다. i+1번을 확인하기 전, 만약 i번이 제대로 도착하지 않는다면 false를 리턴한다.

 

Main 함수

solve(0, 0);
if(ans == INF) System.out.print(-1);
else System.out.print(ans);

0번째 인덱스부터 탐색을 시작하고, 모든 탐색이 종료되면 유효한 최소값인지에 따라 결과를 출력한다.

 

전체 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main{
	
    static int N, H, M, ans;
    static int[][] ladder = new int[30][10]; //행,열 입력값의 최대 크기로 초기화
    static final int LEFT = 2;
    static final int RIGHT = 1;
    static final int INF = 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());
 
		int a, b;
		for(int i=0; i<M; i++) {
			st = new StringTokenizer(br.readLine());
			a = Integer.parseInt(st.nextToken());
			b = Integer.parseInt(st.nextToken());
			ladder[a-1][b-1] = RIGHT;
			ladder[a-1][b] = LEFT;
		}
		solve(0, 0);
		if(ans == INF) System.out.print(-1);
		else System.out.print(ans);
    }
    
    //i번이 i번에 도착하는지 확인하는 함수
	static boolean check() {
		for(int i=0; i<N; i++) {
			int r = 0;
			int c = i;
			do {
				if(ladder[r][c] == LEFT) //가로선 기준 오른쪽일 경우 왼쪽으로 이동
					c --;
				else if(ladder[r][c] == RIGHT) //가로선 기준 왼쪽일 경우 오른쪽으로 이동
					c ++;
				r ++;
			} while(r != H);
			
			if(c != i) return false;
		}
		return true;
	}
    
    //모든 경우의 수를 만들어서 완전탐색
	static int solve(int pos, int cnt) { //인덱스, 추가한 가로선의 개수
		 if(cnt == 3 || pos == N*H) {
			 if(check())
				 return cnt;
			 return INF;
		 }
		 int ret = INF; //최소값을 찾아야하므로 무한대로 초기화
		 int r = pos / N;
		 int c = pos % N;
		 if(c != N-1 && //마지막 열은 가로선을 추가할 수 없음
		ladder[r][c] == 0 && ladder[r][c] == 0) { 
			 ladder[r][c] = RIGHT;
			 ladder[r][c+1] = LEFT;
			 ret = Math.min(ret, solve(pos + 2, cnt + 1)); //다음 pos 인덱스에 이미 가로선을 추가했으므로 한 칸을 건너뛴다.
			 ladder[r][c] = ladder[r][c+1] = 0;
		 }
		 //사다리를 놓지 않았을 때는 cnt를 증가시키지 않고 다음 인덱스로 이동
		ret = Math.min(ret, solve(pos + 1, cnt));
		return ret;
	}
}

 

참고

https://www.youtube.com/watch?v=sPH_4975phU