[알고리즘] 백준 - 사다리 조작

백준 - 사다리 조작

실패한 내 풀이

from itertools import combinations
import sys

N, M, H = list(map(int, input().split()))

graph = [[0] * (N+1) for _ in range(H+2)]
h_record = [0] * (N + 1)
for _ in range(M):
    a, b = list(map(int, input().split()))
    graph[a][b] = 1

possible_pos = []

def go_down(i):
    # print("go down" + str(i))
    cur_pos = [1, i]

    while cur_pos[0] <= H+1:
        # print(cur_pos)
        if graph[cur_pos[0]][cur_pos[1]] == 1: #오른쪽으로 가는 경우
            cur_pos = [cur_pos[0]+1, cur_pos[1]+1]
        elif graph[cur_pos[0]][cur_pos[1]-1] == 1: #왼쪽으로 가는 경우
            cur_pos = [cur_pos[0]+1, cur_pos[1]-1]
        else:
            cur_pos = [cur_pos[0]+1, cur_pos[1]]
    # print(cur_pos)
    return cur_pos[1]

def test():
    for i in range(1, N+1):
        if i != go_down(i):
            return False
    return True

# for comb in list(combinations(possible_pos, ))
def not_adjacent():
    for i in range(1, H + 2):
        for j in range(1, N-1):
            if graph[i][j] == 1 and graph[i][j-1] == 1:
                return False
    return True

def print_graph():
    print()
    for i in range(1, H+2):
        for j in range(1, N):
            print(graph[i][j], end = " ")
        print()
    print()

def dfs(count, y, x, max_count):
    if count == max_count:
        if test():
            print(count)
            exit()
        else:
            return

    for i in range(y, H+2):
        for j in range(1, N):
            if graph[i][j] == 0:
                if j ==1 :
                    if graph[i][j+1] != 1 and h_record[j]+1 <=H and h_record[j+1]+1 <= H:
                        graph[i][j] = 1
                        h_record[j] +=1
                        h_record[j+1] += 1
                        dfs(count+1, i, j, max_count)
                        h_record[j] -=1
                        h_record[j+1] -= 1
                        graph[i][j] = 0
                elif j == N-1:
                    if graph[i][j-1] != 1 and h_record[j]+1 <=H and h_record[j+1]+1 <= H:
                        graph[i][j] = 1
                        h_record[j] +=1
                        h_record[j+1] += 1
                        dfs(count+1, i, j, max_count)
                        h_record[j] -=1
                        h_record[j+1] -= 1
                        graph[i][j] = 0
                else:
                    if graph[i][j-1] != 1 and h_record[j]+1 <=H and h_record[j+1]+1 <= H:
                        graph[i][j] = 1
                        h_record[j] +=1
                        h_record[j+1] += 1
                        dfs(count+1, i, j, max_count)
                        h_record[j] -=1
                        h_record[j+1] -= 1
                        graph[i][j] = 0

if test():
    print(0)
    exit()
else:
    for max_count in range(1, 4):
        for i in range(1, H+2):
            for j in range(1, N):
                if graph[i][j] == 0:
                    if j ==1 :
                        if graph[i][j+1] != 1 and h_record[j]+1 <=H and h_record[j+1]+1 <= H:
                            graph[i][j] = 1
                            h_record[j] += 1
                            h_record[j+1] += 1
                            dfs(1, i, j, max_count)
                            h_record[j] -= 1
                            h_record[j+1] -= 1
                            graph[i][j] = 0
                    elif j == N-1:
                        if graph[i][j-1] != 1 and h_record[j]+1 <=H and h_record[j+1]+1 <= H:
                            graph[i][j] = 1
                            h_record[j] += 1
                            h_record[j+1] += 1
                            dfs(1, i, j, max_count)
                            h_record[j] -= 1
                            h_record[j+1] -= 1
                            graph[i][j] = 0
                    else:
                        if graph[i][j-1] != 1 and graph[i][j+1] != 1 and h_record[j]+1 <=H and h_record[j+1]+1 <= H:
                            graph[i][j] = 1
                            h_record[j] += 1
                            h_record[j+1] += 1
                            dfs(1, i, j, max_count)
                            h_record[j] -= 1
                            h_record[j+1] -= 1
                            graph[i][j] = 0

print(-1)

# H 체크

다른 사람 풀이

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

//https://buddev.tistory.com/23

public class baekjoon_15684 {
    private static int N, M, H, map[][];

    public static void main(String[] args) throws Exception {
        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 = new int[H + 1][N];
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken()) - 1;
            int b = Integer.parseInt(st.nextToken()) - 1;
            map[a][b] = 1;
            map[a][b + 1] = -1;
        }

        if (searchOddNum() > 3) {
            System.out.println("-1");
            return;
        } else {
            for (int i = 0; i <= 3; i++)
                if (dfs(0, 0, 0, i))
                    return;
        }
        System.out.println("-1");
    }

    private static boolean dfs(int x, int y, int cnt, int size) {
        if (cnt == size) {
            if (ladderCheck()) {
                System.out.println(size);
                return true;
            }
            return false;
        }

        for (int i = x; i < H; i++) {
            for (int j = y; j < N - 1; j++) {
                if (map[i][j] != 0 || map[i][j + 1] != 0) continue;

                map[i][j] = 1;
                map[i][j + 1] = -1;
                if (dfs(i, j + 2, cnt + 1, size)) return true;
                map[i][j] = 0;
                map[i][j + 1] = 0;
            }
            y = 0;
        }
        return false;
    }

    private static boolean ladderCheck() {
        for (int j = 0; j < N; j++) {
            int nx = 0, ny = j;

            while (nx <= H) {
                if (map[nx][ny] == 1) ny++;
                else if (map[nx][ny] == -1) ny--;
                nx++;
            }
            if (ny != j) return false;
        }
        return true;
    }

    private static int searchOddNum() {
        int oddNum = 0;
        for (int j = 0; j < N - 1; j++) {
            int num = 0;
            for (int i = 0; i < H; i++)
                if (map[i][j] == 1) num++;
            if (num % 2 == 1) oddNum++;
        }
        return oddNum;
    }
}