백준 1707번 python 풀이 - 이분 그래프

문제 링크

1707번

해결책

import sys
sys.setrecursionlimit(100000)


def dfs(cur, par):
    flag = ""
    if group[par] == 1:
        group[cur] = -1
        flag = -1
    else:
        group[cur] = 1
        flag = 1
    for i in path[cur]:
        if group[i] != 0:
            if group[i] == 1:
                if flag == 1:
                    return False
            elif group[i] == -1:
                if flag == -1:
                    return False
        else:
            if dfs(i, cur) is False:
                return False
    return True


T = int(sys.stdin.readline().rstrip())
ans = []

for __ in range(T):
    V, E = map(int, sys.stdin.readline().rstrip().split())
    path = [[] for _ in range(V + 1)]
    group = [0 for _ in range(V + 1)]

    for _ in range(E):
        _from, _to = map(int, sys.stdin.readline().rstrip().split())
        path[_from].append(_to)
        path[_to].append(_from)

    for i in range(1, V+1):
        if group[i] == 0:
            flg = dfs(i, i)
            if flg is False:
                break
    if flg:
        ans.append("YES")
    else:
        ans.append("NO")

for an in ans:
    print(an)

주석으로 달 설명

이번 역시 DFS 문제. 재귀를 이용한 구현으로 해결했다. 지난번 시험부터 느끼는데, 확실히 stack 형 보다 쉽긴 한데 메모리를 많이 먹는 느낌…? 이번에도 메모리 초과가 자주 발생해서 조금 고생했다. check를 진행하는 것과 그룹을 나누는 것을 합쳐, char가 아닌 1, 0, -1를 이용해서 확인하는 방식으로 수정하니, 괜찮았다. 또한, 그래프가 서로 분리된 경우를 대비해야 함 역시 고려해야 한다.