BJ_ 2668 숫자 고르기, BJ_20040 사이클 게임

문제 링크

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

2668번: 숫자고르기

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

20040번: 사이클 게임

 

---

문제  설명/ 풀이

- 그래프에서 사이클 찾기

사이클을 검출한다는 것은 그래프 내에 사이클이 존재하는지? 있다면 총 몇개가 존재하는지? 사이클에 포함된 노드는 무엇인지? 에 대해 알아내는 것이다.

 

-  무향 그래프에서의 사이클

무향 그래프에서의 사이클은 Union-Find를 통해 구할 수 있다.

union find에서 같은 부모를 가진 노드끼리 union을 하게 되면 사이클이 생긴다고 할 수 있다.

그러므로, 주어지는 입력값들을 계속해서 union 해주면서 같은 부모를 가진 노드끼리 union되는지만 살펴보면 된다.

 

코드:

import sys

sys.setrecursionlimit(10 ** 6)

m, n = map(int, sys.stdin.readline().split())

p = [i for i in range(m)]


def find(x):
    if x == p[x]:
        return x
    p[x] = find(p[x])
    return p[x]


def union(x, y):
    x = find(x)
    y = find(y)

    if x == y:
        return True # 사이클 생기면 true

    # 아니면 작은 쪽으로 union
    elif x > y:
        p[x] = y
        return False
    else:
        p[y] = x
        return False


flag = 0

for i in range(n):
    a, b = map(int, sys.stdin.readline().split())
    if flag != 0: # 한번이라도 사이클이 생기면 입력만 받고 바로 넘김
        continue

    if union(a, b): # 사이클이 생기면 flag 변경
        flag = i + 1

if flag == 0:  # 사이클 x => 0출력
    print(0)
else:
    print(flag) # 사이클 O => 사이클 생긴 지점 출력


### 항상 작은 값 기준으로 혹은 항상 큰 값 기준으로 합치도록 하면,
### 트리의 높이가 낮아져서 시간이 빨라지는 효과가 있습니다.

 

-  유향 그래프에서의 사이클

유향 그래프에서는 DFS를 통해 사이클을 구할 수 있다.

DFS를 돌면서 자기 자신이 나온다면 사이클 안에 갇혀 있는 것이다.

 

코드:

# dfs
import sys

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

# 인접한 노드에 대한 리스트를 만든다
arr = {i: [] for i in range(1, n + 1)} 
for i in range(1,n+1):
    m = int(sys.stdin.readline())
    arr[m].append(i)

# 사이클에 존재하는 노드를 넣을 set
s = set()

for i in range(1,n+1):
    q = []
    if i in arr[i]: # 자기자신으로 그래프가 생기면 사이클 ex. 5->5
        s.add(i)
        continue
    q.extend(arr[i]) # 인접 노드 리스트 넣어주기

    while q:
        new = q.pop()
        if i in arr[new]: # DFS를 돌다가 자기 자신이 나오면
            s.add(i) # 그 노드는 cycle의 구성요소이다.
            break
        q.extend(arr[new])

print(len(s)) # 노드개수
for i in sorted(s): # 노드
    print(i)

---

다른 사람의 풀이

import sys
input = sys.stdin.readline
n = int(input())
num = [0] # 1부터 시작하기 위한 배열
for i in range(n):
    num.append(int(input()))


def dfs(v, i):
    visited[v] = True # 방문처리
    next = num[v] # 다음으로 방문할 노드
    if not visited[next]: # 방문하지 않은 곳 방문
        dfs(next, i)
    elif visited[next] and next == i: # 방문했고, 자기자신인 노드가 나오면 cycle의 구성요소
        result.append(next)

result = list() # 사이클에 존재하는 노드를 넣을 배열

for i in range(1,n+1):
    visited = [False]*(n+1) # 처음에는 방문 x
    dfs(i, i) # i(자기자신)부터 방문

print(len(result))
for r in result:
    print(r)

그래프 방향을 반대로 생각하여 방문 처리를 하여 풀었다.