[백준] G4 15684 사다리 조작 (java)

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

15684번: 사다리 조작

 

풀이

 

1) 사다리를 나타내는 이차원 배열 ladder[][]를 생성한다. 가로선을 나타낼 변수 cnt = 1 생성.

2) cnt를 1씩 증가시키면서 ladder에 가로선을 표시한다.

3) 사다리 게임을 진행하는 함수 boolean isCorrect()를 만든다. 만약 true이면 자기자신으로 돌아오는 경우이며 false일 경우 자기자신으로 돌아오지 않는 경우이다.

3) 문제에서 가로선은 3개까지만 추가할 수 있으므로 0~3까지 모든 경우의 수를 조합으로 구한다.

3-1) 가로선을 추가할 수 있는 모든 경우의 수로 ladder를 초기화 해준 후 isCorrect() 함수를 적용시킨다.

3-2) isCorrect() 를 거치고 모든 지점에서 자기 자신으로 돌아올 경우 끝을 나타내는 isOver 변수를 true 해준후 정답을 출력한다.

3-3) 만약 0~3 까지 모든 경우의 수를 적용시켜도 정답이 안나올 경우 정답은 3보다 큰 경우이므로 -1을 출력한다.

 

주의사항

 

1) 이차원 배열의 좌표를 조합으로 구하기 위해 R*C 까지 1씩 증가하면서 r과 c를 구했다. 여기서 r을 C로 나누지 않고 R로 나누는 멍청한 짓을하면 나처럼 20분을 버리게된다.

 

package com.baekJoon;

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

public class BJ_G4_15684_사다리조작 {
	static BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
	static StringTokenizer tokens;
	static int R,C,M,ladder[][], answer = -1;
	static boolean isOver;
	public static void main(String[] args) throws NumberFormatException, 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][C];
		int cnt = 1;
		for(int m=0; m<M; m++) {
			tokens = new StringTokenizer(input.readLine());
			int r = Integer.parseInt(tokens.nextToken())-1;
			int c = Integer.parseInt(tokens.nextToken())-1;
			ladder[r][c] = cnt;
			ladder[r][c+1] = cnt++;
		}
		for(int i=0; i<=3; i++) {
			combination(0, 0, i);
		}
		System.out.println(answer);
	}
	
	private static void combination(int start, int cnt, int end) {
		if(isOver) return;
		if(cnt == end) {
			if(isCorrect()) {
				answer = end;
				isOver = true;
			}
			return;
		}
		
		for(int i=start; i<R*(C-1); i++) {
			int r = i/(C-1);
			int c = i%(C-1);
			if(ladder[r][c] != 0 || ladder[r][c+1] != 0) {
				continue;
			}
			if(cnt==1 && ladder[r][c] != 0) {
				continue;
			}
			ladder[r][c] = ++M;
			ladder[r][c+1] = M;
			combination(i+1, cnt+1, end);
			ladder[r][c] = 0;
			ladder[r][c+1] = 0;
			M--;
		}
	}

	private static boolean isCorrect() {
		for(int i=0; i<C-1; i++) {
			boolean isVisited[] = new boolean[M+1];
			int r = 0;
			int c = i;
			
			while(true) {
				if(r == R) break;
				if(ladder[r][c] == 0) { // 0 인 경우
					r++;
				}else { // 0 이 아닌 경우 -> 사다리가 연결된 경우
					if(isVisited[ladder[r][c]]) { // 아래로 가는 경우
						r++;
					}
					else if(isIn(r, c+1) && !isVisited[ladder[r][c]] && ladder[r][c] == ladder[r][c+1]) { // 오른쪽으로 가는경우
						isVisited[ladder[r][c]] = true;
						c++;
					}else if(isIn(r, c-1) && !isVisited[ladder[r][c]] && ladder[r][c] == ladder[r][c-1]) { // 왼쪽으로 가는 경우
						isVisited[ladder[r][c]] = true;
						c--;
					}
				}
			}
			if(c != i) {
				return false;
			}
		}
		return true; // 다 돌았는데 이상이 없으면 전부다 자기 번호로 내려온다는 의미!
	}
	
	static boolean isIn(int r, int c) {
		return(r>=0 && c>=0 && r<R && c<C);
	}
	static String src = 
			"5 6 6\r\n"
			+ "1 1\r\n"
			+ "3 1\r\n"
			+ "5 2\r\n"
			+ "4 3\r\n"
			+ "2 3\r\n"
			+ "1 4";
}

 

후기

 

 처음부터 접근방법을 몰랐다면 쉽지 않았을것 같다. 여러 시뮬레이션 문제를 풀면서 이런쪽으로 머리를 굴리는 연습을 해야한다고 느꼈다.

재귀을 도는 중에 답을 찾고 즉시 탈출을 하고 싶을때 바로 나갈 방법을 찾았다. 편법이 있기는 했지만 return으로 탈출하는것이 정석이라고 한다. 꼼수 부리지 말자.