15864 - 사다리 조작

 

---

 

문제

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

15684번: 사다리 조작

 

풀이

 

시간제한이 굉장히 빡센 문제로, 오랫동안 고민한 문제다.

 

내가 처음 풀이했던 방식은 다음과 같다. 

우선 입력을 모두 받고 아래와 같은 형식으로 2차원 배열을 저장한다.

'#' 은 내가 움직일 수 있는 가로선과 세로선을 의미한다.

 

사다리의 이미지를 그대로 그려서 탐색할려 했다. 디버깅도 쉬워보였고..

이후에 사다리를 0개, 1개, 2개, 3개 놓는 모든 상황을 dfs로 만들어주고 탐색을 시작한다.

단 가로선이 연속되지 않도록 검사하면서 놓아주어야 한다.

 

탐색은 '#'를 탐색하면서 좌,우에 사다리가 있다면 이동해주고 없다면 밑으로 내려가는 방식으로 구현했다.

그리고 답이 나오면, 바로 return 한다. 사다리를 적게 놓는 로직부터 돌았으니, 답이 나오면 바로 최솟값이다.

 

결과적으로, 해당 로직은 문제가 없으나 '#' 값을 검사하는 로직이나, 좌우를 검사하는 로직등, 불필요한 로직이 많아서 그런지 시간초과를 벗어날 수 없었다. 코드도 작성하다보니 점점 맛이가서 구조를 아예 엎었다.

 

개선

2차원 배열은 가로선만 저장하는 배열로 컨셉을 바꾸었다.

 

	0	1	2	3
0	0	0	0	0
1	0	1	0	0
2	0	0	1	0
3	0	0	1	0

 

3개의 세로선과, 3개의 가로줄이 있다고 가정해보자

 

1번 세로줄의 1번 가로줄이 1로 명시되어있다.

이 말은 1번 세로줄과 2번 세로줄을 연결해주는 가로줄이 1번에 있다는 뜻이다.

 

2번 세로줄의 3번 가로줄에도 1이 표시되어있다.

이 뜻은 2번 가로줄과 3번을 잇는 가로줄이 3번에 있다는 뜻이다.

따라서 1이 명시되어 있다는 건, 해당 세로줄과 그 다음 세로줄을 잇는 선을 의미한다.

 

구조를 이렇게 바꿈으로써, 가로줄이 연속하는지 쉽게 검사하고 사다리를 놓을지 말지를 정할 수 있다.

좌상단부터 검사하며 본인의 위치값이 1이거나, 내 오른쪽 값이 1이라면 사다리를 설치할 수 없기에 넘어간다. (연속되므로)

그 외에 본인 위치값이 0이면서 오른쪽 값도 0이면 해당 위치에 사다리를 설치하면 된다!

 

탐색 같은 경우에는 밑으로 내려가면서 탐색하면 되는데, 현재 위치값에 1이 있다면 우하단으로 내려가고,

왼쪽에 값이 있다면 좌하단으로 내려가면 된다.

( 3번 세로줄이라고 가정했을 때, 3번 세로줄에서 1이 있다면 3 <-> 4 를 연결하는 줄이고, 2번 세로줄에서 1이 있다면 

  2<->3을 연결하는 줄이기에 검사해보고 넘어가야한다.)

 

 

코드

from sys import stdin

def search(x, y):
    global ladder, n, m
    target = y
    # 세로로 탐색이 끝날때 까지
    while x <= m:
        # 오른쪽으로 가는 가로선이 있다면
        if ladder[x][y] == 1:
            x += 1
            y +=1
        # 왼쪽으로 가는 가로선이 있다면
        elif ladder[x][y-1] == 1:
            x +=1
            y -=1
        else:
            x +=1

    if y == target:
        return True
    return False

def dfs(cnt, limit):
    global ladder
    if cnt == limit:
        for i in range(1, n+1):
            if not search(1, i):
                return 
        print(cnt)
        exit(0)

    for i in range(1, m+1):
        for j in range(1, n):
            if ladder[i][j] == 0:
                if ladder[i][j+1] == 1:
                    continue
                ladder[i][j] = 1
                dfs(cnt+1, limit)
                ladder[i][j] = 0

# Initialize
n, h, m = map(int, stdin.readline().rstrip().split())
ladder = [ [0] * (n+1) for _ in range(m+1)]
for _ in range(h):
    x, y = map(int, stdin.readline().rstrip().split())
    ladder[x][y] = 1

for i in range(4):
    dfs(0, i)

print(-1)

 

후기

 

접근하는데에는 크게 문제가 없었다. 로직도 사실상 비슷하다. 그러나 구현이라 생각하고 너무 원론적이고 비효율적인 코드를 짠게  패착이었던 거 같다. 시간초과과 계속되면 전반적인 구조를 바꾸는것에 대하여 생각하자.