[DFS] 백준 구슬 찾기 2617번 with Python3

illustrated  by  あすてろid  https://www.pixiv.net/users/2033916

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

2617번: 구슬 찾기

문제

 

내 풀이

import sys
input = sys.stdin.readline
# recursion error 시 최대 재귀 깊이를 늘려주면 해결 될 지도?
sys.setrecursionlimit(10000000)

# 동빈나식 dfs


def dfs(graph, v, visited):
    global count, ans
    visited[v] = True
    # 종료 조건
    if count == (n+1)//2:
        return

    # print(v, end=" ")

    for i in graph[v]:
        if visited[i] == False:
            # 1. 방문한 적이 없고,
            # 2. 현재 v 노드에서 i노드로 간선이 연결되어있다면
            count += 1
            dfs(graph, i, visited)


# 입력창
n, m = map(int, input().split())

# 메모리 초과 문제로 nxn이 아니라 각 인덱스에 연결된 노드 값 추가
graph_big2smol = []
for _ in range(n+1):
    graph_big2smol.append([])

graph_smol2big = []
for _ in range(n+1):
    graph_smol2big.append([])

# 2 1, 5 3 식의 노드 연결관계를 각 인덱스에 추가
for _ in range(m):
    a, b = map(int, input().split())
    graph_big2smol[a].append(b)
    graph_smol2big[b].append(a)


# 방문 확인용 리스트
# visit_big = [False] * (n + 1)
# visit_smol = [False] * (n + 1)
# 더 크거나 작은 노드 개수 확인용
# count = 0
# 매 노드마다 초기화해야하기에 for문 안으로 옮겨줬다.

# 문제별 추가 코드
ans = [0] * (n + 1)

# 함수 실행
for k in range(1, n+1):
    count = 0
    visit_big = [False] * (n + 1)
    dfs(graph_big2smol, k, visit_big)
    # 자기보다 큰 노드가 n+1//2 보다 크다 = 절대 중심이 될 수 없다.
    if count >= (n+1)//2:
        ans[k] = 1

for j in range(1, n+1):
    count = 0
    visit_smol = [False] * (n + 1)
    dfs(graph_smol2big, j, visit_smol)
    if count >= (n+1)//2:
        ans[j] = 1

# 정답 출력
print(ans.count(1))

해설

정말 오랜만에 아예 아무것도 안보고 풀었다.

처음에는 dp 알고리즘을 활용해 풀어야하나 싶었지만 그래도 dfs로 풀어보고 싶어서 구상한 알고리즘은 이렇다.

 

1. 특정 구슬 a가 중심이 절대 안되는 경우는 자신보다 무겁거나 가벼운 구슬의 개수가 (n+1)//2 보다 크거나 같을 때이다.
2. input으로 들어오는 인과 관계를 두 그래프로 나눠 넣어, 구슬 a가 b보다 더 무거울 때, 구슬 a가 b보다 가벼울 때의 방향성을 활용 할 수 있게 준비했다.
3. 모든 구슬마다 dfs 함수를 두 번씩 실행해 1번 조건에 해당하는지를 탐색했다.
4. 결과적으로 ans 리스트에 각 index에 해당하는 구슬이 가능한지 불가능한지가 1과 0으로 저장되어있다.