119. [삼성기출15]Python 백준 15684 번 사다리조작 자세한 설명

안녕하세요 코딩하는 덕구입니다.

백준 15684 번 사다리조작 입니다.

 

먼저 백준 15684 번 사다리조작 정답 코드입니다. 설명은 아래에 있습니다.

n, m, h = map(int, input().split())
board = [[False for _ in range(n + 1)] for _ in range(h + 1)]
for _ in range(m):
    a, b = map(int, input().split())
    board[a][b] = True

def dfs(depth, x, y):
    global ans
    if ans <= depth:
        return
    if check():
        ans = min(ans, depth)

    for i in range(x, (h + 1)):
        if x != i:
            y = 1
        for j in range(y, n):
            if not board[i][j]:
                board[i][j] = True
                dfs(depth + 1, i, j + 2)
                board[i][j] = False
    return

def check():
    for i in range(1, n + 1):
        loc = i
        for j in range(1, h + 1):
            if board[j][loc]:
                loc += 1
            elif board[j][loc - 1]:
                loc -= 1
        if loc != i:
            return False
    return True

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

 

문제 접근

1. dfs 를 통해 다리 3개까지 놓는 모든 경우의 수를 생각한다.

2. 각 경우마다 마다 사다리 조작이 재대로 되었는지 확인한다.

3. 최소값을 업데이트 한다.

 

Python 코드 구현

 

사다리를 구현합니다.

n, m, h = map(int, input().split())
board = [[False for _ in range(n + 1)] for _ in range(h + 1)]
for _ in range(m):
    a, b = map(int, input().split())
    board[a][b] = True

 

answer 의 줄임말인 ans 에는 최소 값을 저장합니다. 맨 처음에는 4로 초기화 합니다.

최소 다리 개수를 업데이트 하는 재귀함수 dfs를 구현합니다.

1. 사다리의 다리는 3개 까지 추가가 가능하므로 4개 이상이면 함수를 실행시키지 않습니다.

2. ans보다 다리 개수가 많으면 return 합니다.

3. check를 통해 사다리 조작이 되었다면 ans와 현재 사다리의 다리 개수를 비교하여 최소값을 ans에 업데이트 합니다.

 

for문 에서는 다리를 놓을 수 있는 모든 위치에 다리를 놓고 depth(다리 개수)를 1 추가 한 후 dfs를 재귀적으로 실행시킵니다.

x != i 일때 y=1인 이유는 x(높이)가 달라지면 1부터 다시 체크해야되기 때문입니다.

j + 2인 이유는 다리는 같은 가로선에 이어서 놓을 수 없기 때문입니다.

 

def dfs(depth, x, y):
    global ans
    if ans <= depth:
        return
    if check():
        ans = min(ans, depth)

    for i in range(x, (h + 1)):
        if x != i:
            y = 1
        for j in range(y, n):
            if not board[i][j]:
                board[i][j] = True
                dfs(depth + 1, i, j + 2)
                board[i][j] = False
    return

 

 

ans가 4이면 (업데이트 되지 않았단 이야기는 4 이상의 사다리가 필요하단 뜻 이므로)

-1 출력

아니라면 ans를 출력합니다. 

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

 

파이썬 백준 15684 번 사다리조작 최종 코드입니다. 

n, m, h = map(int, input().split())
board = [[False for _ in range(n + 1)] for _ in range(h + 1)]
for _ in range(m):
    a, b = map(int, input().split())
    board[a][b] = True

def dfs(depth, x, y):
    global ans
    if ans <= depth:
        return
    if check():
        ans = min(ans, depth)

    for i in range(x, (h + 1)):
        if x != i:
            y = 1
        for j in range(y, n):
            if not board[i][j]:
                board[i][j] = True
                dfs(depth + 1, i, j + 2)
                board[i][j] = False
    return

def check():
    for i in range(1, n + 1):
        loc = i
        for j in range(1, h + 1):
            if board[j][loc]:
                loc += 1
            elif board[j][loc - 1]:
                loc -= 1
        if loc != i:
            return False
    return True

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

 

백준 15684 번 사다리조작 자세한 설명 및 Python 코드였습니다.

감사합니다.