[ 백준 ] 1867 돌멩이 제거 파이썬 풀이

// 문제 요약

 

n x n 격자의 운동장에 k 돌멩이가 있다.

격자 하나당 둘 이상의 돌멩이가 있을 수 없을 때

하나의 행이나 열을 따라 직선으로 달려가며 돌멩이를 주워

모두 줍는 최소 달리기 수를 구하여라

 

// 사고

 

처음에는 그때 그때 열과 행의 모든 돌멩이 수를 구하고

거기서 가장 많은 돌멩이가 있는 열 혹은 행을 따라 돌멩이를 지우며

제귀적으로 풀이하는 Greedy 방식을 사용했다.

아래의 방법은 결과적으로 실패했다.

 

### 백준 1867 돌멩이 제거
# https://www.acmicpc.net/problem/1867

n, k = map(int, input().strip().split(" "))

board = [[0 for _ in range(n)] for _ in range(n)]

for _ in range(k):
    i, j = map(int, input().strip().split(" "))
    board[i-1][j-1] = 1

clear_count = [0]
def stone_clear():
    rsl = get_raw_sum_list()
    csl = get_col_sum_list()

    if not (sum(rsl) + sum(csl)):
        return

    if max(rsl) > max(csl):
        clear_raw(rsl.index(max(rsl)))
    else :
        clear_col(csl.index(max(csl)))
    clear_count[0] += 1

    stone_clear()

def get_raw_sum_list():
    rtn = []
    for i in range(n):
        rtn.append(sum(board[i]))
    
    return rtn

def get_col_sum_list():
    rtn = []
    for j in range(n):
        c = 0
        for i in range(n):
            c += board[i][j]
        rtn.append(c)
    
    return rtn

def clear_raw(index):
    for j in range(n):
        board[index][j] = 0
    return board

def clear_col(index):
    for i in range(n):
        board[i][index] = 0
    
    return board

stone_clear()
print(clear_count[0])

이 코드를 제출했을 때 결과는 시간초과가 아니고 '답이 틀림'이었다.

 

틀린 케이스를 어떻게 구할지 한참을 고민하다가 구글에 검색하고

아래의 블로그를 찾았다. 감사의 말씀을 전한다.

https://cocoon1787.tistory.com/819

[C++] 백준 1867번 - 돌멩이 제거

 

사실 내 입장에서는 블로그 내용을 전체 다 이해하는 것이 어려웠다.

그래서 내 나름대로 정리를 다시 해보려고 한다.

출처 : https://cocoon1787.tistory.com/819

이런 경우에서는 각 행 혹은 열에서 구해지는 최대 돌멩이 값(여기서는 2)이

행, 열에 걸쳐 여러개 나타난다는 문제가 발생한다.

그러므로 그때 그때 어떤 행, 혹은 열을 따라야하는지

최대값 만으로는 최적의 해를 구해내는 것이 불가능 하다.

 

예컨데 가로로만 달리도록 하면 위의 케이스에서는 3회에 끝나지만

세로로 먼저 줍도록 하면 4회가 걸리게 된다.

그런데 위의 케이스를 90도 회전하면 세로로 달리는 것이 정답이 된다.

 

이런 분기는 어디서 발생하느냐하면

어떤 돌멩이가 가로와 세로 모든 방향으로 줍는 것이 가능할 때 발생한다.

 

예를 들어 위의 (3,2) 돌멩이는 그리디하게 작성한 코드에서는

3행을 따라 달리는 경우로도 줍는 것이 가능하고

2열을 따라 달리는 경우로도 줍는 것이 가능하다.

이처럼 경로가 겹쳐져 있는 돌멩이의 경우

어떤 규칙으로 주워야 할 것인가를 생각하는 것이 이번 문제의 핵심이다.

 

그리고 그 방법은 위의 블로그에서 아주 상세하게 잘 나와있으니 참고하기 바란다.

 

// 풀이

 

코드를 보자.

### 백준 1867 돌멩이 제거
# https://www.acmicpc.net/problem/1867

n, k = map(int, input().strip().split(" "))

stones = {row:[] for row in range(1, 1+n)}
for _ in range(k):
    row, col = map(int, input().strip().split(" "))
    stones[row].append(col)

bipartite_matching = [False for _ in range(1+n)]

def dfs(i):

    if visited[i]:
        return False
    visited[i] = True

    for j in stones[i]:
        i_to_j = bipartite_matching[j]
        if i_to_j == False or dfs(i_to_j) == True:
            bipartite_matching[j] = i
            return True
    
    return False

c = 0
for i in range(1, 1+n):
    visited = [False for _ in range(1+n)]
    if dfs(i) :
        c += 1

print(c)

 

정말 무수히 많이 틀렸다...

파이썬은 0 == False 라서 조건문과 인덱스를 함께 쓸때는 반드시 주의해야 한다.

이 문제의 포인트는 row 와 col 을 노드로 가지고

반드시 row와 col 끼리만 연결되는 특수한 트리를 생각하면 된다.

그리고 1대 1 대응으로 최대 연결 개수를 구할 수 있는

dfs를 찾아주면 된다.