[백준 15684번] 사다리조작(파이썬)

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

15684번: 사다리 조작

 

이 문제에서 해결해야할 것은

 

1. 사다리 줄을 어떻게 구현할 것인가

 

2. 어떻게 사다리 줄을 추가로 그리는 걸 구현할 것인가

 

크게 두 개입니다.

 

문제에서 요구한 데로

저렇게 code로 구현하는 것이 가장 좋습니다.

 

 

'만약에 줄이 이어지는 거니깐

예를들어 1 2 라인이 이어지면

1 1로 표현하는 거 어떤가요??'

 

실제로 제가 처음 문제를 접근했을 때

이렇게 구현을 시도했습니다.

저는 길찾기 문제에 익숙했었기 때문에

그래프로 길찾을 때

저렇게 이어지는 식으로 구하자고 했습니다.

그런데 이렇게 구하면

나중에 그래프를 새로 그릴 때 문제가 생깁니다.

제가 오류가 났었던 부분입니다.

저렇게 그래프를 구현하고 나고 그래프를 그릴 때

예시의 오류가 발생합니다.

실제로는 1-2 3-4이렇게 이어진 건데

컴퓨터가 코드를 읽을 때에는

'1-2-3-4'가 연속되어있네?

라고 생각하기 쉽습니다.

그래서 맨 처음의 케이스로 해야

이상없이 그래프를 구현할 수 있습니다.

 

가로선을 추가로 구현하는 건

백트래킹+dfs조합으로 풀 수 있습니다.

다행히, 문제에서 3개까지만 그릴 수 있다고하니

모든 경우를 다 그릴 필요는 없습니다.

다만, 너무 정직하게 구하면 시간초과가 또 날 수 있는데요

 

for point in range(N - 1):
    n_y = point
    for h in range(H):
        nx = h
        flag = 0
        if graph[h][point] == 1:
            continue
        # 줄을 추가하기전에, 주변에 다른 줄이 없는지 판별
        for d in range(2):
            ny = n_y + dy[d]
            if ny < 0 or ny >= N:
                continue
            if graph[nx][ny] == 1:
                flag = 1
                break
        if flag == 0:
            graph[h][point] = 1
            dfs(depth + 1)
            graph[h][point] = 0

 

 

저는 이런식으로 구현을 했는데

이 방식이 시간초과로 떴습니다.

이 부분에 대한 수정은

전체 코드를 보면서 함께 보겠습니다.

 

# 백준 15684 사다리 조작
import sys

N, M, H = map(int, input().split())
graph = [[0] * N for _ in range(H)]
line = [[] for _ in range(H)]
min_len = 4

dy = [1, -1]


def dfs(depth, x, y):
    global min_len
    if depth > 3:
        return
    # print(graph)
    go = 0
    # 현 상태에서 줄을 쭉 따라갈 때의 경우를 생각한다.
    for i in range(N):
        ny = i
        for nx in range(H):
            # 오른쪽에 줄이 있을 경우
            if graph[nx][ny] == 1:
                ny += 1
            # 왼쪽에 줄이 있는 경우
            elif ny > 0 and graph[nx][ny - 1] == 1:
                ny -= 1
        if ny == i:
            continue
        else:
            # print("no")
            go = 1
            break

    if go == 0:
        min_len = min(min_len, depth)
        return
    # 만약 뭔가 삐꾸가 났다면 줄을 추가한다
    if go == 1:
        for i in range(x, H):
            k = y if i == x else 0  # 같은 세로줄 확인하면 y부터, 아니면 0부터
            for j in range(k, N - 1):
                if graph[i][j] == 0:
                    flag = 0
                    # 현재 이을려는 줄이, 가로로 연속한지 판별

                    for d in range(2):
                        ny = j + dy[d]
                        if ny < 0 or ny >= N:
                            continue
                        if graph[i][ny] == 1:
                            flag = 1
                            break
                    if flag == 1:
                        continue

                    graph[i][j] = 1
                    dfs(depth + 1, i, j + 2)
                    graph[i][j] = 0


for i in range(M):
    a, b = map(int, sys.stdin.readline().split())
    graph[a - 1][b - 1] = 1
dfs(0, 0, 0)
if min_len == 4:
    print(-1)
else:
    print(min_len)

dfs를 해주면서

선을 그린 y 좌표+2를 해주면서

중복을 피하고 있습니다.

이렇게 해주면서

케이스가 줄어들어

의도적으로 시간초과를 줄여나갈 수 있었습니다.

 

그래프를 구현할 때

어떻게 접근해야할지

다른 시각을 주었던 좋은 문제입니다.

 

(내용추가:2022.10.14)

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

if M==0:
    print(0)
    exit(0)

radder=[[0]*N for _ in range(H)]
answer=4
def dfs(depth,nx,ny):
    global answer,radder
    if depth>3:
        return
    if depth>answer:
        return

    #먼저 현재 사다리 기준 다 내려가는지 보자
    flag=True
    for y in range(N):
        sy=y
        for x in range(H):
            # print(x,sy)
            if radder[x][sy]:
                sy+=1

            elif sy-1>=0:
                if radder[x][sy-1]:
                    sy-=1

        if not sy==y:
            flag=False
            break
    #다 맞는 번지에 내려왔다면 최소값 갱신
    if flag:
        answer=min(answer,depth)
        return
    #그게 아니라면 줄 추가

    else:

        for x in range(nx,H):
            if x==nx:
                k=ny
            else:
                k=0
            for y in range(k,N-1):
                #현재 지점에 사다리가 놓여졌다면
                if radder[x][y]:
                    continue
                #이전 세로줄에 사다리가 놓여있다면(단, y-1>=0일떄만 체크)
                if y-1>=0 and radder[x][y-1]:
                    continue

                radder[x][y]=1
                dfs(depth+1,x,y)



for _ in range(M):
    a,b=map(int,input().split())
    if b==N:
        continue
    radder[a-1][b-1]=1
# for x in range(H):
#     print(radder[x])
# print()

dfs(0,0,0)
if answer==4:
    print(-1)
else:
    print(answer)

 

가독성 및 시간초과를 줄인 코드.

이전에는 사다리를 넣는 조건이

다시 보니깐 복잡해보이네요.

이번에는 심플하게

현재 위치의 세로줄에 줄이 있는지

그 왼쪽 세로줄에 줄이 있는지

두 개만 체크했습니다.

이전 코드를 보니 

사다리 넣는 조건이 너무 복잡한 느낌이네요.

그냥 간단하게

현재시점기준 왼/오에 사다리가 있냐 없냐

그것만 판단하면 됩니다.

마지막 줄은 사다리를 넣을 수 없으니

마지막 전의 줄까지만 체크하면 되고요.

이전의 방법은 제가 다시 읽어도

약간 복잡한 느낌이 들고

가독성도 너무 떨어지네요.

문제에 대한 이해도가 높을수록

코드도 간결해지고 보기 쉬워지는 느낌.