🥚문제

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

• 구현
• 브루트포스 알고리즘
• 백트래킹

---

🥚입력/출력

---

🍳코드

# 출처: https://ryu-e.tistory.com/69
import sys
input = sys.stdin.readline

# i번 세로선의 결과가 i번이 나오는지 체크하는 함수
def check():
    for dest in range(1, N+1):
        col = dest
        for row in range(1, H+1):
            if arr[row][col]:
                col += 1
            elif 0 <= col-1 and arr[row][col-1]:
                col -= 1
        
        if col != dest:
            return False
    return True


def dfs(cnt, r, c):
    global ans
    
    if check():
        ans = min(ans, cnt)
        return
    
    # cnt가 3이면 다음에는 4를 검사해야하므로 중단
    # ans < cnt이면 최소값이 아니므로 중단
    if cnt == 3 or ans < cnt:
        return
    
    for i in range(r, H+1):
        # 가로선을 우선적으로 탐색한다
        if i == r:
            # 행이 변경되기 전에는 c열에서부터 탐색
            k = c
        else:
            # 행이 변경될 경우 1열에서부터 탐색
            k = 1
        
        for j in range(k, N):
            if not arr[i][j]:
                # 가로선을 긋고, 연속된 가로선을 긋지 않기 위해 j + 2를 호출한다
                arr[i][j] = True
                dfs(cnt + 1, i, j+2) # cnt 1 증가, 세로선은 그대로, 연속해서 두 사다리가 오면 안되므로 가로선은 2 증가
                arr[i][j] = False



# main
N, M, H = map(int, input().split())
arr = [[False]*(N+1) for _ in range(H+1)]

# 가로선 입력
for _ in range(M):
    a, b = map(int, input().split())
    arr[a][b] = True

ans = 4
dfs(0, 1, 1)
if ans <= 3:
    print(ans)
else:
    print(-1)

---

🧂아이디어

구현

출처: https://ryu-e.tistory.com/69

• 시간초과 해결 위해 위 출처 글 참고!

• 어떤 정점 (r, c)에서 시작해서 dfs를 통해 가로선을 그을 수 있는지 탐색하는 방법으로 풀었다.

• (r, c)에서 탐색을 시작할 때, 가로를 먼저 탐색한다 (r행부터 ~ N행까지 탐색)

• check() 함수를 통해 i열이 i에 도착하는 것을 확인하면 추가된 가로선의 개수인 cnt와 ans의 값을 비교해서 작은 것을 ans에 저장한다. (최소로 가로선을 추가해야 함)

• 또, 현재 cnt가 3이거나, cnt가 현재 ans보다 커서 최소값을 만족시키지 못하면 중단한다.

• 이외의 경우에는 (r, c)에서 추가할 수 있는 가로선이 있는지 탐색한다.

• 이때, (r, c)와 동일한 행 r행을 탐색할 때는, c열에서부터 탐색해주면 되지만
  (r, c)와 다른 행(r+1행 ~ N행까지)을 탐색할 때는 1열에서부터 탐색해줌에 유의한다.

• 행을 우선적으로 탐색 -> 그 행 안에 있는 열들을 탐색한다.
  (dfs 함수 내부의 이중 for문 구조 확인하기)

• 위 과정을 통해 도달한 (i, j) 위치에 가로선이 없다면 이 위치에 가로선을 긋고, 연속된 가로선을 긋지 않기 위해 다음 탐색은 (i, ⭐️j+2⭐️)에서 시작한다.

• dfs함수의 실행을 마치면 ans값을 확인하고
  • 3보다 작거나 같으면 ans를 출력
  • 그렇지 않으면 -1을 출력