[IT/코딩테스트] 99클럽 코테 스터디9일차 TIL + BOJ1707

 

오늘의 문제

https://www.acmicpc.net/problem/1707

골드4

 

오늘의 문제는 일단 정답 비율이 24.959% 로 시작부터 겁을 먹게 만들었다.

떨리는 마음을 붙잡고 문제를 읽었는데 이해가 안 갔다. 

 

이분 그래프??? 이게 뭐지

 

저번에 항해에서 제공해주신 강의를 들었을 때, 그래프의 종류로 이분그래프를 얼핏 들었던 것 같았는데.

기억이...  ㅎㅎ  그래서 처음에는 그래프를 다 그렸을 때, 그 상태에서 대칭으로 나눌 수 있는지(?) 라고 이해했다. 약간 데칼코마니 처럼...

 

그런데 그렇게 생각을 하니까 아무리 구현을 해보려고 해도 풀이를 생각할 수가 없었다. 

 

그래서 우선 이분 그래프에 대해서 알아보기로 했다.

아래의 글에서 공부할 수 있었고 바로 어떤 식으로 풀어야할지 감이 왔다.

 

https://didu-story.tistory.com/271

[알고리즘] 이분그래프란? (특징, 탐색방법) (feat. BFS,DFS)

 

---

나의 첫 번째 풀이 (실패)

노드 마다 방문 + 두 종류의 그룹 중에 어디에 속하는지 체크해가며 탐색한다면 해결할 수 있을 것이라 생각했다.

아, 노드 방문 방식은 dfs를 생각했다.

 

1. dfs 에 현재의 노드와 그룹의 값을 준다.

2. 해당 노드의 방문을 우선 체크해준다. 배열의 해당 노드 인덱스에 그룹값을 저장한다.

3. 그리고 그 노드와 연결되어 있는 인접 노드를 탐색한다. 

4. 만약 인접 노드가 방문하지 않은 곳이라면 dfs 를 실행한다. 그룹값은 - 를 붙여서 준다.

5. 만약 인접 노드가 방문한 곳이라면, 그 값이 현재 노드의 그룹값과 같은지 확인한다.

- 같으면 False 리턴

- 다르면 pass

6. 이분 그래프임을 전부 확인했으면 True 리턴 

 

위의 dfs 를 가지고 문제를 풀 수 있도록 실행 for 문 작성.

 

그렇게 작성한 코드를 파이참에서 실행해보았고, 올바르게 동작하는 것을 확인한 후에 백준 사이트에 입력했다.

그런데 결과는 ..... 

 

ㅠㅠ

 

다시 만난 런타임에러....

이번엔 RecursionError 가 원인이었다.

 

링크를 눌러서확인해보니 재귀 관련 에러였다.

지정되어 있는 깊이보다 훨씬 더 깊게 탐색을 해버리면 나타난다고 한다.

 

https://help.acmicpc.net/judge/rte/RecursionError

에러 설명

 

 

그리고 아래에 두가지의 해결 방법이 작성되어 있었는데, 

1) 재귀 함수를 사용하지 않고 구현하기
: 만약 dfs 로 구현했다면 bfs 로 구현해보자! 다이나믹 프로그래밍이라면 반복문으로 구현하자!

2) sys.setrecursionlimit()을 사용하기
: 이 함수를 사용하면, Python이 정한 최대 재귀 갚이를 변경할 수 있다. 소스 1의 최대 재귀 깊이를 1,000,000 정도로 크게 설정하면 런타임 에러 없이 실행된다.
(단, 설정할 수 있는 최댓값을 크게 변경했다고 하더라도, 재귀의 깊이가 채점 서버가 감당할 수 없는 정도로 깊어지면, Segmentation fault가 발생해 런타임 에러 이유로 SegFault를 받게된다.)

 

 

나는 2번을 채택했다.

물론, 임시방편일 수도 있지만 우선 dfs 로 구현을 했으니 끝까지 dfs 로 마무리를 짓자는 생각이었다.

( bfs로는 나중에 하보는 걸로....)

 

---

나의 두 번째 풀이 (성공)

아래는 작성한 전체 코드이다.

import sys
sys.setrecursionlimit(10**6)

k = int(sys.stdin.readline())


def dfs(start, group):
    visited[start] = group # 현재 노드가 어느 그룹에 속하는지 저장
    # 인접 노드를 탐색한다.
    for node in graph[start]:
        # 만약 인접 노드가 방문하지 않은 곳이라면 dfs 실행, 그룹 반대값으로 지정
        # 만약 인접 노드가 방문한 곳이라면 그 값이 현재 노드의 그룹과 같은지 다른지 확인
        # 같으면 FALSE 리턴, 다르면 pass
        if visited[node] == 0:
            result = dfs(node, -group)
            if not result:
                return False
        else:
            if visited[node] == visited[start]:
                return False
    return True


for _ in range(k):
    v, e = map(int, sys.stdin.readline().split())
    graph = [[] for _ in range(v + 1)]
    visited = [0] * (v + 1)
    for _ in range(e):
        a, b = map(int, sys.stdin.readline().split())
        graph[a].append(b)
        graph[b].append(a)

    # 노드 순서대로 확인
    for i in range(1, v + 1):
        if not visited[i]:
            result = dfs(i, 1)
            if not result:
                break

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

 

 

정답~! 해결 완료 했다. 🤭🔥

 

이진 탐색을 공부했을 저번주와는 다르게 이번주는 더 힘든 것 같다.

DFS, BFS 가 나에게는 너무 어려운 것 같기도 하고... ㅎㅎ

 

그치만 하나하나 알아가고 공부하고 예시를 쌓아가는 것 같아서 뿌듯하다.

아마 이 코테 스터디가 끝나도 계속 이런식으로 문제를 풀어갈 것 같다!!