고... 골드가 풀린다!...

그래프 문제를 푸는 날이었다.

 

먼저 풀었던 아이는 

#1260번 DFS와 BFS https://www.acmicpc.net/problem/1260

1260번: DFS와 BFS

무난하게 해결! 

개념을 확립하는데 큰 도움이 됐다!

 

DFS는 재귀,

BFS는 Queue를 통해 해결하는게

가장 좋은 것 같아.

 

간혹 BFS로 해결하는게 유리한 문제에서 DFS를 사용하면 recursionError이 발생하는데, 파이썬에서 설정한 재귀의 한계깊이에 도달하면 발생하는 문제이다.

이를 해결하기 위해 sys.setrecursionlimit()을 통해 한계를 늘려주는 경우도 있는데

그냥 BFS를 사용하는게 더 좋다.

 

그 다음으로 풀었던 문제는 

 

#11724번 연결 요소의 개수  https://www.acmicpc.net/problem/11724

11724번: 연결 요소의 개수

모든 요소들이 연결되지 않은 경우를 찾는 문제이다. 나는 다음과 같이 while문을 통해 해결했다.

import sys
N, M = map(int, input().split())
graph = [[] for _ in range(N+1)]

for _ in range(M):
    prev, to = map(int, sys.stdin.readline().split())
    graph[prev].append(to)
    graph[to].append(prev)

visited = [False]*(N+1)
queue = []


def dfs(start):
    visited[start] = True
    queue.append(start)

    while queue:
        prev = queue.pop(0)

        for n in graph[prev]:
            if not visited[n]:
                visited[n] = True
                queue.append(n)


answer = 1
dfs(1)
while sum(visited) < N:
    for i in range(1, N+1):
        if not visited[i]:
            dfs(i)
            answer += 1

print(answer)

마지막 while 부분에서 검증되지 않은 노드들을 추가로 탐색하면서 그래프의 총 개수를 센다.

 

그리고 위 방법을 다음 문제에 적용했다.

 

 

#1707 이분그래프 https://www.acmicpc.net/problem/1707

1707번: 이분 그래프

이분 그래프 여부를 판단하는 문제이다.

이분 그래프 : 2가지 색으로 인접노드들을 구분할 수 있는 그래프

 

1) 노드들을 탐색하며 색을 칠하고 (현재 노드의 색과 다음 노드의 색을 다르게)

2) 색이 칠해져있는 노드를 만났을 때 칠하고자 하는 색과 동일한지 판단한다.

 2-1) 아닐 경우에 NO!

 2-2) 맞을 경우에는 그냥 지나치기

 

3) 모든 노드가 하나로 연결되어 있지 않을 수도 있으므로, 11724번 문제에서 진행했던 방식을 추가해준다.

import sys
t = int(input())
for i in range(t):

    # make graph
    v, e = map(int, input().split())
    graph = [[] for _ in range(v+1)]
    for _ in range(e):
        prev, to = map(int, sys.stdin.readline().split())
        graph[prev].append(to)
        graph[to].append(prev)

    # print graph
    # for i in range(v+1):
    #     print(i, graph[i])

    # bfs
    visited = [0]*(v+1)
    queue = []
    result = "YES"

    def bfs(start):
        global result
        queue.append(start)

        while queue:
            # print(visited)
            prev = queue.pop(0)
            for n in graph[prev]:
                if not visited[n]:
                    visited[n] = -1 if visited[prev] == 1 else 1
                    # print(n, visited, visited[prev] == 1)
                    queue.append(n)
                else:
                    if visited[prev] == visited[n]:
                        result = "NO"
                        return

    visited[1] = 1
    bfs(1)
    # print(visited)
    while 0 in visited[1:]:
        for i in range(1, v+1):
            if not visited[i]:
                visited[i] = 1
                bfs(i)
    # print(visited)

    print(result)

이후 다른 답안들을 찾아보다 보니

 

내가 연속해서 사용했던 방법 (그래프의 단일화 여부를 파악)이 약간 비효율적이라는 느낌을 받았다.

    for j in range(1, v+1):
        if not visited[j]:
            bfs(j)
    # print(visited)

이렇게 작업하는게 더 효율적이다. 굳이 루프를 두번 돌릴 필요가 없다!

 

오늘은 만족스러운 풀이였다.