[백준_15684번] 사다리 조작

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

15684번: 사다리 조작

[문제]

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

 

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

 

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

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

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

 

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이 증가한다.
• 입력으로 주어지는 가로선이 서로 연속하는 경우는 없다.

 

[코드]

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

public class BaekJoon_15684 {
	static int[][] map;
	static int n,m,h,result;
	static boolean finish=false; // 끝나야 하는 조건을 만족했는가 확인하는 변수
	public static void main(String[] args) throws Exception {
		// TODO Auto-generated method stub
		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 배열은 각 세로선과 가로선의 교차하는 지점, 즉 가로선이 시작될 수 있는 칸을 의미한다.
		 * 0 : 가로선 없음
		 * 1 : 오른쪽으로 이동
		 * 2 : 왼쪽으로 이동
		 */
		map=new int[h+1][n+1];
		
		for(int i=0;i<m;i++) {
			st=new StringTokenizer(br.readLine());
			/*
			 * b번 세로선과 b+1세로선을 a 점선 위치에서 연결
			 * map[a][b]칸에서는 오른쪽으로 이동해야하고, map[a][b+1]칸에서는 왼쪽으로 이동해야함
			 */
			int a=Integer.parseInt(st.nextToken()); 
			int b=Integer.parseInt(st.nextToken()); 
			
			map[a][b]=1;
			map[a][b+1]=2;
		}
		
		// 설치할 사다리의 개수는 0~3개
		for(int i=0;i<=3;i++) {
			// 설치할 사다리의 개수를 전역변수로 저장하고 dfs의 재귀 깊이가 해당 수만큼 진행되도록 한다.
			result=i;
			dfs(0,1);
			if(finish) // 중간에 만족하는 경우가 있다면 종료
				break;
		}
		
		System.out.println((finish)?result:-1);
	}
	
	static void dfs(int line, int start) {
		if(result==line) { // result 개수만큼 가로줄을 만들었다면
			if(check()) // 조건을 만족하는지 확인하여 finish 값을 바꿔준다.
				finish=true;
			
			return;
		}
		
		// 맵을 전체 탐색하면서 가로선 세우기
		for(int i=start;i<=h;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;
					dfs(line+1,i); // 가로선의 갯수 +1, 다음 탐색 위치를 매개변수로 재귀호출
					map[i][j]=map[i][j+1]=0; // 값 복귀
				}
			}
		}
	}
	
	// i번 세로선의 결과가 i번이 나오는지 확인하는 함수
	static boolean check() {
		for(int i=1;i<=n;i++) { // 각 세로줄 탐색
			int nx=1; // 시작하는 가로줄
			int ny=i; // 시작하는 세로줄
				
			while(nx<=h) { // 가로줄의 끝까지 탐색
				if(map[nx][ny]==1) ny++; // 오른쪽으로 이동해야 하는 경우
				else if(map[nx][ny]==2) ny--; // 왼쪽으로 이동해야 하는 경우
				nx++; // 다음줄로 내려가기
			}
			// 가로줄의 끝에 내려간후 i번 세로선의 결과가 i번이 나오는지 확인
			if(ny!=i) return false; 
		}
			
		return true;
	}
}

 

[고찰]

 이번 문제와 같이 배열의 칸이 아닌 라인을 다루는 문제는 어떻게 배열에 대입해야 할지 막막해 다른 사람의 포스팅을 보고 풀이 아이디어를 얻었다. 이번 문제에서 배열을 사용하여 각 배열에 저장되는 값은 세로줄과 가로줄의 교차점의 값이다. 세로줄과 가로줄의 교차점에는 가로줄이 생성될 수 있는 곳으로 배열 값이 0이면 가로줄이 없는 상황, 1이면 오른쪽으로 이동해야 하는 가로줄, 2면 왼쪽으로 이동해야 하는 가로줄을 의미한다. 여기까지 설정이 끝났다면 나머지는 그렇게 어렵지는 않은 문제였다. 

 

*** 1) 추가 가로줄 설치(dfs 함수)

        1-1) 추가로 설치될 수 있는 가로줄은 3개이지만 최소 개수를 구해야하기 때문에 0개부터 3개까지 dfs 함수의 재귀 종료 조건으로 설정한다.(result 변수)

        1-2) 배열 전체를 탐색하면서 가로줄이 설치되어 있지 않은 칸에 가로줄을 설치한다.

        1-3) 설치된 가로줄의 개수가 result와 같아진다면 해당 경우가 종료조건(i번 세로선의 결과가 i번이 나와야 하는지)을 만족하는지 확인한다.

 

*** 2) 사다리가 설치된 상황에서 조건을 만족하는지 확인(check 함수)

        이 부분은 특별한 알고리즘 없이 구현 부분이다. 각 세로줄이 가로줄을 타고 내려갔을 때 결과가 자신과 같아지는지 확인한다.

 

이번 문제는 배열의 의미를 파악하는 부분이 가장 어려웠고, check 함수를 구현하는 부분에서도 시간이 좀 걸렸다. 아직 구현 부분이 많이 미숙하다는 걸 느낀다.