문제

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

나의 코드

"""

"""

from sys import stdin
input = stdin.readline

n, m, h = map(int, input().split())
pan = [ [0] * (n+1) for _ in range(h+1) ]
horizon_line = [ list(map(int, input().split())) for _ in range(m) ] # 가로선의 정보
ladder_position = []
answer = 4

for a, b in horizon_line: # 가로선의 정보를 기록
    pan[a][b] = 1

for i in range(1, h+1): # 백트래킹을 돌면서 가로선을 놓을 좌표를 기록한다. (가로선을 놓을려면 양옆으로 가로선이 없어야 놓을 수 있다.)
    for j in range(1, n):
        if pan[i][j-1] == 0 and pan[i][j+1] == 0 and pan[i][j] == 0:
            ladder_position.append((i, j))

def ladder_down(): # 사다리를 내려가는 함수

    for i in range(1, n+1):
        now = i
        for j in range(1, h+1):
            if pan[j][now] == 1: # 오른쪽으로 이동
                now += 1
            elif pan[j][now-1] == 1: # 왼쪽으로 이동
                now -= 1

        if now != i: # i번 세로선이 i번 그대로 나오지 않으면 False를 return한다.
            return False

    return True # i번 세로선이 i번 그대로 나온다면 True를 return한다.

def line_arrange(depth, idx): # 가로선을 배치하는 함수
    global answer

    if ladder_down(): # 사다리를 내려가는 함수를 통해 True가 return이 되면 최소값을 갱신한다. (depth == 가로선을 배치한 개수)
        answer = min(answer, depth)
        return

    if depth == 3 or depth >= answer: # 만약 가로선이 4개가 넘거나 현재 최소값보다 클 경우 return
        return

    for i in range(idx, len(ladder_position)): # 미리 가로선을 놓을 수 있는 좌표를 이용해서 백트래킹 한다.
        x, y = ladder_position[i]
        if pan[x][y-1] == 0 and pan[x][y+1] == 0: # 백트래킹 과정중에 양옆에 가로선이 생겼을 수도 있으므로 다시 한번 확인한다.
            pan[x][y] = 1
            line_arrange(depth+1, i+1)
            pan[x][y] = 0

line_arrange(0, 0)
print(answer if answer < 4 else -1)
    

설명

백트래킹을 이용해 모든 경우의 수에 대해 탐색할줄 알아야 한다.

그리고 ladder_down() 함수의 알고리즘도 다시한번 볼만하다.

또한 line_arrange()의 if ladder_down()과 if depth == 3 or depth >= answer: 부분의 위치가 서로 바뀌면 오답이 나온다.
이유는 계속 생각해봐도 잘 모르겠다;;

• 4시간 넘게 걸린 문제

참고 자료