15684_사다리조작

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

15684번: 사다리 조작

 

 

생각보다 되게 까다로운 문제였다...

 

 

2차원 배열을 하나 잡는데 이는 각 사다리간 사이에 사다리가 놓여져 있는지, 비어져 있는지를 나타낸다.

 

예를들어

위와같이 3개 사다리중에 2개만 연결되어 있다면

 

0 0 0 0

0 1 0 0

0 0 1 0

0 0 0 0

 

와같은 배열을 나타낸다. 이때 아래를 제외하고 0으로 감싸주면서 만드는 이유는 그래야 나중에 사다리를 놓을지 안놓을지 검사할때 index에러에서 조금 자유롭기 때문

 

나는 처음 문제를 고민할때 큰 실수를 했다. 먼저, dfs를 사용해서 모든 경우를 뒤지는 경우 사다리를 고르고 '다음' 사다리를 기준으로 놓을지 안놓을지를 고민했는데 문제를 잘 읽어보면 같은 칸의 옆의 자리만 보고 놓을지 안놓을지를 정해지게 되어 있다. 이를 잘 확인해야한다.

 

맨 처음 고민할때는 사다리를 놓을 수 있는곳을 리스트에 넣고 이를 dfs로 할까 하다가 그냥 nx,ny를 구해서 비교하려고 했는데 이 접근이 잘못되어서 예외처리가 너무 많이 나왔다...

 

import sys
input = sys.stdin.readline

n,m,h = map(int,input().split())

ladder = [ [0] * (n+1) for _ in range(h+1)]
for _ in range(m):
    a,b = map(int,input().split())
    ladder[a][b] = 1


def check_end(start):
    for i in range(1,h+1):
        if ladder[i][start-1] == 1:
            start = start - 1
        elif ladder[i][start] ==1:
            start = start + 1
    return start

def check_game():
    for i in range(1,n):
        if check_end(i) != i:
            break
    else:
        return True
    return False



result = (n-1) * h - m + 1
def dfs(x,y,cnt,flg):
    global result

    # for i in ladder:
    #     print(i)
    # print(x,y,cnt)
    # print(check_game())
    # print('------------')

    if result <= cnt:
        return
    if check_game():
        result = cnt
        return
    else:
        if x == n and y==h-1:
            ladder[x][y]=1
            if check_game():
                result = cnt+1
                return
            ladder[x][y]=0
            return

    if 0<y<n-1:
        ny = y+1
        nx = x
    elif 0<x<h:
        nx = x+1
        ny = 1
    else:
        return

    if ladder[x][y] == 1:
        if ny == 1:
            dfs(nx,ny,cnt,0)
        else:
            dfs(nx,ny,cnt,1)
        return

    if not flg and ladder[x][y+1]==0:
        ladder[x][y] = 1
        dfs(nx,ny,cnt+1,1)
        ladder[x][y] = 0
        dfs(nx,ny,cnt,0)
    else:
        dfs(nx,ny,cnt,0)

dfs(1,1,0,0)



print(-1 if result == (n-1) * h - m + 1 else result)

 

실제로 코드가 통과되지도 않는다 ㅡ,ㅡ 

 

혼자 계속 고민하다가 결국 블로그를 조금 보니까 내가 처음에 생각한 리스트를 넣을 수 있는 배열을 미리 만들어두는 방법이 맞았고 이를 적용하여 통과할 수 있었다...