[골드 3] 사다리 조작

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

15684번: 사다리 조작

시발 문제 리뷰 안 할 수가 없다 진짜 헤맸다

1. 일단 가로세로 한번 헷갈렸음

2.  사다리 존재를 1로만 표시했더니 좀 어려웠다 차라리 왼쪽을 1 오른쪽을 2로 표기하자

푸는 방식

1. (놓을 수 있는 자리) C (0,1,2,3) 조합 문제이다

2. 나는 왼쪽을 기준으로 오른쪽으로 그을 거다 그러니까 오른쪽에 출발 1 이 있는지만 체크하면 됨

 

제일 해맨부분

for(int i = last_i ; i < ~

for(int j = last_j+1 ; j < ~

 

평소 last_pick +1부터 탐색하는 조합 기법을 사용했었는데

이거는 j를 넘어서 i가 1개 추가되면 바보같이 j를 0부터가 아닌 last_j+1 그러니까

덜 탐색하게 되는 방식이었다

과감하게 int j = 0부터로 바꿔주자  하지만 더 탐색하는 경우가 생기긴 하겠다 

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

public class Main {

	public static boolean find_can = false;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		StringTokenizer st;

		int N, M, H;
		int[][] arr; // 0은 밑으로 내려가 1은 오른쪽으로이동 2은 왼쪽으로 이동

		st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		H = Integer.parseInt(st.nextToken());
		arr = new int[H][N];

		for (int i = 0; i < M; i++) {
			st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());

			arr[a - 1][b - 1] = 1;
			arr[a - 1][b - 1 + 1] = 2;
		}

		///////////////////////////////////////////////////////////

		// (0개 놓았을때 놓을 수 있는 경우의 수) C (0,1,2,3);

		int answer = -1;

		for (int r = 0; r <= 3; r++) {
			recursion(arr, r, 0, 0, -1);
			if (find_can) {
				answer = r;
				break;
			}
		}

		System.out.println(answer);
	}

	public static void recursion(int[][] arr, int r, int depth, int last_i, int last_j) {

		if (depth == r) {
			boolean can = true;

			for (int j = 0; j < arr[0].length; j++) {
				if (j != where_is_my_goal(arr, j))
					can = false;
			}

			if (can)
				find_can = can;

			return;
		}

		for (int i = last_i; i < arr.length; i++) {
			for (int j = 0; j < arr[0].length - 1; j++) {
				if (arr[i][j] == 0) {

					// 오른쪽에 출발 사다리 있어
					if (arr[i][j + 1] == 1) {
						continue;
					}
					arr[i][j] = 1;
					arr[i][j + 1] = 2;
					recursion(arr, r, depth + 1, i, j);
					arr[i][j] = 0;
					arr[i][j + 1] = 0;
				}
			}
		}

	}

	public static int where_is_my_goal(int[][] arr, int start) {
		int x = start;
		for (int i = 0; i < arr.length; i++) {
			if (arr[i][x] == 1) {
				x = x + 1;

			} else if (arr[i][x] == 2)
				x = x - 1;
		}

		return x;
	}
}