[백준 15684] 사다리 조작 (Python)

 

www.acmicpc.net/problem/15684

15684번: 사다리 조작

문제풀이

N, M, H : 입력값(세로선의 개수, 가로선의 개수, 가로선을 놓을 수 있는 위치)

board : 특정 지점 방문 여부 체크

ans : 가로선을 놓은 최소 개수(결과값)

 

check() : i번 세로선이 i번으로 잘 도착하였는지 확인하는 함수

dfs(cnt, x, y) : 재귀적으로 가로선을 놓을 수 있는 곳에 다 놓는 함수, cnt - 현재까지 가로선을 놓은 개수, x - 행, y - 열

 

 

골드 5 문제인데 생각보다 까다로운(?) 문제이다. 특히 가로선과 세로선을 잘 구별해야 한다.

문제에서 N은 세로선의 개수인데, 코드로 작성할 때 N은 배열에서 행이 아닌 열이다. 이 부분을 주의해야 한다.

 

 

1. 현재 상태에서 모든 세로선이 출발점에서 도착점으로 잘 도착하는지 확인한다.

정상적으로 도착하면 ans 값을 갱신하고 return

정상적으로 도착하지 않으면서 cnt(현재 가로선을 놓은 개수) 가 3이거나 (cnt가 3이면 다음 호출에서 cnt가 4가 되기 때문에 문제 조건에 위배) cnt가 ans보다 크면 return

 

2. 가로선을 놓는다. (board[i][j] = True)

가로선을 놓을 때 반복문을 사용하게 되는데, 행 for문을 우선적으로 해야하는 것을 유의해야 한다.(가로선을 놓아야 하기 때문에 행 for문 안에 가로선(열) for문이 있어야한다)

놓을 가로선을 탐색할때는 임시변수로 k를 두었는데, 재귀호출이기 때문에 행이 변경되기 전 가로선을 이어서 탐색하기 위함이다.

가로선을 놓을 때 -- 와 같은 형태를 만들면 안되므로 if문을 통해 해당 조건을 배제하였다.

 

3. 놓았던 가로선을 없앤다. (모든 경우를 다 해봐야 하기때문에 => 브루트포스)  (board[i][j] = False)

 

4. 모든 가로선을 놓아볼때까지 1-3 과정을 반복한다. 

 

 

코드

import sys

# 브루트포스로 가로선을 놓을 수 있는 곳에 가로선을 놓아보면서 매번 출발점에서 도착점으로 정상 도착 하는지 확인해야한다.
# N, M, H 제한이 크지 않아서 통과한 것 같다.
# 가로선과 세로선을 잘 구별해야한다. 문제에서 N은 세로선의 개수인데, 코드로 작성할 때 N은 배열에서 행이 아닌 열이다.

def check(): # i번 세로선이 i번으로 도착하는지 확인
    for start in range(N): # 1번부터 N번 세로선(열)까지 검사
        k = start # k는 이동하는 가로선
        for j in range(H): # 가로선(행) 이동
            if board[j][k]: # 가로선이 존재한다면
                k += 1 # 가로선 오른쪽으로 한칸 이동
            elif k > 0 and board[j][k - 1]: # 가로선이 왼쪽에 존재한다면
                k -= 1 # 가로선 왼쪽으로 한칸 이동
        if k != start: return False # 가장 하단까지 왔는데 k가 start랑 같지 않으면 정상 도착하지 않은 것이므로 return False
    return True

def dfs(cnt, x, y):
    global ans
    if check(): # 현재 상태에서 각 출발점이 도착점으로 잘 도착하는지 확인
        ans = min(ans, cnt)
        return
    elif cnt == 3 or ans <= cnt: # 도착점이 정상적이지 않으면
        # cnt 값이 3일 경우 그 다음 호출에서 cnt가 4가 되어 문제 조건 위반하므로 return
        # cnt 값이 ans 보다 크거나 같을 경우에는 그 다음 경우를 볼 필요가 없으므로 return
        return
    # 행
    for i in range(x, H):
        # 가로선을 우선으로 탐색하므로
        if i == x: k = y # 행이 변경되기 전에는 가로선을 계속해서 탐색
        else: k = 0 # 행이 변경될 경우 가로선 처음부터 탐색
        for j in range(k, N - 1): # 세로선(열)
            if not board[i][j] and not board[i][j + 1]: # 가로선을 놨을 때 오른쪽에 -가 존재하지 않는 경우
                if j > 0 and board[i][j - 1]: continue # 가로선을 놨을 때 왼쪽에 -가 존재할 경우 continue (--가 되면 안되기 때문)
                board[i][j] = True # 가로선 놓기
                dfs(cnt + 1, i, j + 2) # cnt 1 증가, 세로선 그대로, -- 이 되면 안되므로 가로선은 2증가
                board[i][j] = False # 가로선 없애기

if __name__ == '__main__':
    N, M, H = map(int, sys.stdin.readline().split())
    board = [[False] * N for _ in range(H)] # 특정 지점 방문 여부 체크
    if M == 0: # M이 0일 경우 출발점에서 도착점으로 바로 내려오므로 0 출력 후 종료
        print(0)
        exit(0)
    for _ in range(M):
        a, b = map(int, sys.stdin.readline().split())
        board[a - 1][b - 1] = True
    ans = 4 # 결과값 4로 초기화
    dfs(0, 0, 0)
    print(ans if ans < 4 else -1)

 

결과

 

위 풀이는 'suri78' 님의 파이썬 풀이를 참고한 코드입니다.

https://suri78.tistory.com/212

 

문제풀이나 코드에서 이상한 부분 지적은 언제나 환영합니다!