[BJ]15684 사다리조작

BJ_G4_15684_사다리조작

 

 

 

문제링크

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

15684번: 사다리 조작

* 일단 문제를 정독 하고 1시간 이상 반드시 고민이 필요합니다.

 

동영상 설명

1시간 이상 고민 했지만 아이디어가 떠오르지 않는다면 동영상에서 약간의 힌트를 얻어봅시다.

BJ G4 15684 사다리조작 - YouTube

 

 

소스보기

동영상 설명을 보고도 전혀 구현이 안된다면 연습 부족입니다.
소스를 보고 작성해 본 후 스스로 백지 상태에서 3번 작성해 볼 의지가 있다면 소스를 살짝 보세요.

package bj.gold.l4;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StringReader;
import java.util.StringTokenizer;

/**
 * @author 은서파
 * @since 2020. 7. 30
 * @see https://www.acmicpc.net/problem/15684
 * @performance 13736	272, 싹수 노란 녀석들 제거: 13700	96	
 * @category #완탐
 * @memo
 */

public class BJ_G4_15684_사다리조작{
	
	static BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
	static StringBuilder output = new StringBuilder();
	static StringTokenizer tokens;
	
	static int C, M, R;
	static int [][] ladder;
	public static void main(String[] args) throws IOException {
		input = new BufferedReader(new StringReader(src));
		tokens = new StringTokenizer(input.readLine());
		C = Integer.parseInt(tokens.nextToken());
		M = Integer.parseInt(tokens.nextToken());
		R = Integer.parseInt(tokens.nextToken());
		
		ladder = new int [R+1][C+1];
		for(int m=0; m<M; m++) {
			tokens = new StringTokenizer(input.readLine());
			int a = Integer.parseInt(tokens.nextToken());
			int b = Integer.parseInt(tokens.nextToken());
			ladder[a][b] = 1; // 가로선의 시작점
			ladder[a][b+1] = -1; // 가로선의 맞은 편
		}// 입력 처리 완료
		
		// 싹수가 노란 녀석은 버리기
		if(getOddCnt() >3) {
			System.out.println(-1);
			return;
		}	
		
		// 0~3개까지 가로선을 추가해보면서 게임이 끝나는지 살펴보자.
		for(int i=0; i<=3; i++) {
			// i 개수만큼 가로선 추가해보기
			boolean result = makeLine(1, 1, i, i);
			if(result) {
				return;
			}
		}
		// 아직 안끝났다면? 
		System.out.println(-1);
		
	}
	
	/**
	 * lineCnt 만큼의 선을 그어가보면서 선택이 완료되면 check 호출로 결과 확
	 * @param sr 출발점 row
	 * @param sc 출발점 col
	 * @param toChoose 골라야할 개수
	 * @param lineCnt 고르기로 한 개수
	 * @return
	 */
	private static boolean makeLine(int sr, int sc, int toChoose, int lineCnt) {
		if(toChoose==0) {
			if(check()) {
				System.out.println(lineCnt);
				// 정답을 골랐으니 더이상 재귀 돌 필요 없어요~~~
				return true;
			}
			return false;
		}
		
		for(int r=sr; r<=R; r++) {
			for(int c=sc; c<C; c++) {
				if(ladder[r][c]==0 && ladder[r][c+1]==0) {
					ladder[r][c]=1;
					ladder[r][c+1]=-1;
					// 가지치기
					if(makeLine(r, c+2	, toChoose-1, lineCnt)) {
						return true;
					}
					
					ladder[r][c]=0;
					ladder[r][c+1]=0;
					
				}
			}// row 하나 체크 완료
			// row가 변경되면 col은 1부터 시작해야 한다.
			sc=1;
		}
		
		
		return false;
	}
	
	
	
	/**
	 * 사다리의 모든 컬럼에서 출발했을 때 도착지가 출발점의 세로선과 일치하는지 반환
	 * @return
	 */
	private static boolean check() {
		for(int c=1; c<=C; c++) {
			int nc = c; // 이동하고 있는 컬럼의 좌표
			for(int r=1; r<=R; r++) {
				// 1이면 오른쪽으로, -1이면 왼쪽으로
				if(ladder[r][nc]==1) {
					nc++;
				}else if(ladder[r][nc]==-1) {
					nc--;
				}
			}// 해당 c에 대한 체크 완료!!
			if(c !=nc) {
				return false;
			}
		}
		return true;
	}
	
	private static int getOddCnt() {
		int oddLine = 0;
		for(int c=1; c<C; c++) {
			int num=0;
			for(int r=1; r<=R; r++) {
				if(ladder[r][c]==1) {
					num++;
				}
			}
			if(num%2==1) {
				oddLine++;
			}
		}
		return oddLine;
	}
	
	// REMOVE_START
	private static String src = "5 6 6\n"
								+ "1 1\n"
								+ "3 1\n"
								+ "5 2\n"
								+ "4 3\n"
								+ "2 3\n"
								+ "1 4";
	// REMOVE_END
	
}