오늘 한 일💪

• 알고리즘 문제 풀이

1707번: 이분 그래프

정말 사소한 이유로 디버깅에 엄청 오래 걸린 문제다... (함께 코드 봐주신 분들 정말 감사합니다.)

문제가 있는 코드

from sys import stdin as s
from collections import deque

s = open("input.txt", "rt")

K = int(s.readline())

now_color = 1  # 1: RED, 0: None, -1: FALSE
is_success = True
node = []


def color(_i):
    global now_color
    if node[_i] == 0:
        node[_i] = now_color
        now_color = -now_color
    elif node[_i] == now_color:
        now_color = -now_color
    elif node[_i] != now_color:
        return True


for t in range(K):
    V, E = map(int, s.readline().rstrip().split())
    node = [0] * (V + 1)

    for i in range(E):
        start, end = map(int, s.readline().rstrip().split())
        if color(start):
            is_success = False
            break
        if color(end):
            is_success = False
            break

    if is_success:
        print("YES")
    else:
        print("NO")

일단 본인의 생각은 이분 그래프의 특징을 생각해서 입력받을 때마다 색을 구분해서 지정하다 충돌이 발생하면 바로 NO라고 출력하려고 했다.

문제1. 순서대로 입력값이 오지 않을 수도 있다.
예제는 작은 것부터 큰 순서로 증가했지만, 실제로는 순서가 바뀌어 들어올 수도 있다. 또 각 노드들끼리 연결되지 않는 경우도 있어 현재 들어온 입력만으로 판단하는 것은 어렵다.

문제2. index error
정말 충격적인 원인이었다.🤯

...
for t in range(K):
    V, E = map(int, s.readline().rstrip().split())
    node = [0] * (V + 1)

    for i in range(E):
        start, end = map(int, s.readline().rstrip().split())
        if color(start):
            is_success = False
            **break**
        if color(end):
            is_success = False
            **break**

    if is_success:
        print("YES")
    else:
        print("NO")

중간에 *로 감싼 break문을 확인해보자. 입력할 때마다 판단하니 break를 만날 수 있다.

그렇다면, 다음 입력을 확인해보자.

2    -> 테스트 케이스 횟수
3 2  -> 첫번째 테스트 케이스(노드, 간선)
2 3  -> ⭐️만약! 현재 입력에서 break문을 만난다면?!⭐️
1 3  
4 4  -> 두번째 테스트 케이스(노드, 간선)
1 2
3 4
4 2
2 3

예제의 3번째 줄처럼 케이스 중간에 break문은 만난다면 어떻게 될까?
첫번째 케이스가 바로 종료되기 때문에 다름에 오는 1,3을 두번째 테스트 케이스의 노드, 간선으로 판단할 것이다.
이런 이유로 index error가 터진 것이다...
이것을 못찾아서 계속 답답했는데, 다른 동료들과 함께 보다가 찾아 주셨다. 정말 감사했다!

오늘부터 본격적으로 문제 풀이를 시작했는데 일단 BFS, DFS 둘다 풀이 방식을 연습하고 있다. 생각보다 시간이 걸리긴하지만, 지금 아니면 또 언제 이렇게 연습해보겠어~ 하는 생각이다.

어제 계획한 오전, 점심, 저녁 구분은 생각보다 어려웠다. 아무래도 코딩이 그냥 딱하면 딱 끝나는게 아니라 더욱 그런 것 같기도 하다.
좋은 방법을 고민해야겠다. 🤨