글 읽기 - 뭐가 틀렸는지 모르겠습니다...

dnatuna 5년 전 0

테스트케이스 어떤 것을 넣어봐야 알 수 있을까요??

어디서 틀린건지 모르겠습니다.

import sys

n, k = map(int, sys.stdin.readline().split())
ground = [[0]*n for i in range(n)]
score_a = dict(zip([i for i in range(n)], [0 for i in range(n)]))
score_b = dict(zip([i for i in range(n)], [0 for i in range(n)]))

for i in range(k):
    a, b = map(int, sys.stdin.readline().split())
    ground[a-1][b-1] = 1
    score_a[b-1] += 1
    score_b[a-1] += 1

dol, ans = 0, 0

while(dol != k):
    if(max(score_a.items(), key = lambda x: x[1])[1] >= max(score_b.items(), key = lambda x: x[1])[1]):
        a = max(score_a.items(), key=lambda x: x[1])[0]
        for i in range(n):
            if(ground[i][a] == 1):
                ground[i][a] = 0
                score_a[a] -= 1
                score_b[i] -= 1
                dol += 1

        ans += 1
    else:
        b = max(score_b.items(), key=lambda x: x[1])[0]
        for i in range(n):
            if (ground[b][i] == 1):
                ground[b][i] = 0
                score_a[i] -= 1
                score_b[b] -= 1
                dol += 1

        ans += 1

print(ans)

evenharder 5년 전 1

밑의 예시가 답이 4가 나와야 합니다.
이 문제는 가장 많은 걸 돌을 포함하고 있는 행과 열을 선택하는 그리디 알고리즘으로는 해결할 수 없습니다.

다른 질문글에도 나와 있지만, 본 문제는 기본적으로 minimum vertex cover와 Kőnig's theorem을 이용해야 합니다.

5 8
1 1
2 2
4 4
5 5
1 3
2 3
4 3
5 3
    
/*
x.x..
.xx..
.....
..xx.
..x.x
*/

dnatuna 5년 전 0

헐.. 감사합니다. ㅠㅠ 완전 접근부터 틀렸군요

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

뭐가 틀렸는지 모르겠습니다...

dnatuna 5년 전 0

evenharder 5년 전 1

dnatuna 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말