[백준] 15684 사다리 조작

📖 문제

---

🧑🏻‍💻 풀이 과정

1) 문제 접근 및 이해

문제를 풀이하기 위하여 몇가지 조건 사항을 구현해야 했습니다.

1. 어느 한 열에서 출발하여 본인의 열로 돌아와야 한다.
2. 가로 선이 연속으로 설치 되어서는 안된다.
3. 가로선은 최대 3개까지 설치가 가능하고, 최소로 설치해야한다.

1번 조건을 위해 사다리 정보를 표현하는 2차원 배열을 만들었고, 가로선이 만들어지면 2개의 좌표가 영향을 받습니다.

그리하여 가로선이 생기는 두개의 좌표에서 좌표를 기준으로 오른쪽에 가로선이 생기면 1을 기록하고 왼쪽으로 생기면 -1을 기록하였습니다.

이러한 값 설정으로 열에서 사다리를 타고 내려올 때, 좌표의 값에 따라 오른쪽이나 왼쪽으로 이동 여부를 판별할 수 있었습니다.

또한, 변수의 증가량 여부에 따라 원래 본인 열로 돌아오는지도 쉽게 판별이 가능했습니다.

 

2번 조건을 해결하기 위하여 가로선을 설치할 수 있는 집합을 생성하였고, 집합의 하나의 요소는 (왼쪽 좌표, 오른쪽 좌표)의 방식으로 기록하였습니다.

그리고 문제에서 주어진 가로선이 나왔을 때, 연속으로 이어지지 않도록 왼쪽과 본인, 오른쪽 가로선의 요소들을 모두 제거하였습니다.

이러한 과정을 통해 주어진 가로선과 연속으로 이어지지 않으며 가로선이 설치 가능한 집합만 남게 되었습니다.

 

마지막 조건을 위하여 조합을 이용하였습니다.

최솟값을 우선적으로 구하기 위하여 요소의 결합은 0부터 3까지 순서대로 탐색하였습니다.

그리고 추가적으로 가로선이 연속으로 설치되면 안되니 설치되는 좌표를 집합으로 따로 확인하여 하나의 좌표에서 양방향으로 가로선이 생기는 경우가 있는지를 추가적으로 판별하였습니다.

2) 알고리즘

• 구현
• 완전탐색

3) 풀이 코드

사용 언어 - Python

import sys
from itertools import combinations
sys.stdin = open('input.txt')

def solution():                         # 모든 열이 본인 열로 되돌아 오는지 확인
    for c in range(N):                  # 모든 열을 반복하며 확인
        ans = 0                         # 현재 열의 위치 (상대적, 양수이면 오른쪽, 음수는 왼쪽)
        for r in range(H):              # 행이 하나씩 증가
            ans += ladder[r][c+ans]     # 해당 좌표의 값을 더함
        if ans:                         # 변수의 값이 0이 아니라면 본인 열로 되돌아가지 못한것
            return False
    return True                         

N, M, H = map(int, sys.stdin.readline().split())                    # 열, 주어진 가로선, 행의 개수
ladder = [[0] * N for _ in range(H)]                                # 사다리 정보
# 사다리 설치 가능한 목록 (왼쪽 좌표, 오른쪽 좌표)
can = {((i, j), (i, j+1)) for j in range(N-1) for i in range(H)}
answer = 0

for _ in range(M):
    a, b = map(int, sys.stdin.readline().split())

    ladder[a-1][b-1] = 1                            # 해당 좌표에서 오른쪽으로 가는 사다리
    ladder[a-1][b] = -1                             # 해당 좌표에서 왼쪽으로 가는 사다리
    # 가로선이 연속할 수 없으므로, 왼쪽과 본인, 오른쪽의 좌표를 모두 제거
    can.difference_update((((a-1, b-2), (a-1, b-1)), ((a-1, b-1), (a-1, b)), ((a-1, b), (a-1, b+1))))
    
for k in range(4):                          # 최대 3개를 놓을 수 있으므로
    for element in combinations(can, k):    # 가로선을 놓을 수 있는 좌표들로 조합을 구함
        chk = set()                         # 가로선이 연속으로 이어지지 않았는지 확인을 위한 변수
        for e in element:                   
            chk.update(e)                   # 가로선이 연결된 왼쪽, 오른쪽 좌표 추가
            ladder[e[0][0]][e[0][1]] = 1    # 왼쪽 좌표에서는 오른쪽 방향 숫자 추가
            ladder[e[1][0]][e[1][1]] = -1   # 오른쪽 좌표에서는 왼쪽 방향 숫자 추가

        if k * 2 == len(chk):               # 가로선이 연속으로 이어지지 않았다면 (좌표가 겹치는게 없다면)
            if solution():                  # 모든 열이 본인 열로 돌아오는지 확인
                print(k)                    # 정답 출력 및 프로그램 종료
                exit(0)

        for e in element:                   # 오답이므로 가로선 놓은것 되돌리기
            ladder[e[0][0]][e[0][1]] = 0
            ladder[e[1][0]][e[1][1]] = 0
print(-1)                                   # 조건으로 불가능한 경우 출력

---

🔗 문제 링크

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

15684번: 사다리 조작

 

 

※ 오류 및 오타, 다른 의견이 있는 경우 댓글을 남겨주시면 감사하겠습니다