[Python] 그래프 문제 풀이 정리(1)

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

# 내 풀이
import sys
sys.setrecursionlimit(2000)

T = int(input())

def find(a):
    if a==parent[a]:
        return a
    else:
        parent[a]=find(parent[a])
        return parent[a]
    
def union(a,b):
    a = find(a)
    b = find(b)
    if a!=b:
        parent[b]=a

for _ in range(T):
    N = int(input())
    n_list = list(map(int, input().split()))
    ans = set()

    parent = [0]*(N+1)
    for i in range(0, N+1):
        parent[i] = i

    for i in range(len(n_list)):
        union(i+1, n_list[i])

    for i in range(1, len(n_list)+1):
        ans.add(find(i))
    print(len(ans))

• union-find를 이용해서 같은 집합에 속한 노드를 찾고 set()을 이용하여 저장했다.

set() 예시

# 다른 풀이(DFS)
import sys
sys.setrecursionlimit(2000)

T = int(input())
def dfs(x): #DFS 함수 정의
    visited[x] = True #방문 체크
    number = arr[x] #다음 방문 장소
    if not visited[number]: #방문하지 않았다면
        dfs(number) #재귀

for _ in range(T):
    cnt = 0
    n = int(input())
    visited = [0] * (n + 1)
    arr = [0]+list(map(int, input().split()))

    for i in range(1, n+1):
        if not visited[i]: #방문하지 않았다면
            dfs(i) #DFS실행
            cnt += 1 #결과값 += 1
    print(cnt)

• DFS로도 풀 수 있다. 노드 리스트(arr)에서 DFS가 몇번 실행되는지 count한다.
• 그래프 이론보다 빠름!

 

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

• 모르겠당...그래프랑 관련을..

# 정답 풀이
import sys
from collections import deque
input = sys.stdin.readline

# 총 층수, 강호가 위치한 곳, 스타트 링크 장소, 위로 U층 이동, 아래로 D층 이동
F, S, G, U, D = map(int, input().split())
visited = [0 for i in range(F+1)]
count = [0 for i in range(F+1)]

def bfs(v):
    q = deque([v])
    visited[v] = 1
    while q:
        v = q.popleft()
        if v == G:
            return count[G]
        for i in (v+U, v-D): #U만큼 위로 or D만큼 아래로
            if 0 < i <= F and not visited[i]:
                visited[i] = 1
                count[i] = count[v] + 1
                q.append(i)
    if count[G] == 0:
        return "use the stairs"
    
print(bfs(S))

• BFS 활용 문제. count 리스트에는 해당 노드에 도착했을 때 누른 버튼의 횟수가 담긴다.
• v+U 혹은 v-D로 계속해서 deque에 추가.
• 목표 노드 G에 도달했을 때의 count[G] 혹은 count[G]==0일 때 출력한다.

 

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

# 정답 풀이
import sys
from collections import deque
input = sys.stdin.readline

N, M = map(int, input().split())
lands = []
visited = [[-1] * M for _ in range(N)] 
for _ in range(N):
    lands.append(list(map(int, input().split())))

dx = [-1,1,0,0]
dy = [0,0,-1,1]

def bfs(i,j):
    queue = deque()
    queue.append((i,j))

    visited[i][j] = 0

    while queue:
        x, y = queue.popleft()
        
        for i in range(4):
            nx, ny = dx[i] + x, dy[i] + y
            
            if 0 <= nx < N and 0 <= ny < M and visited[nx][ny] == -1:
                if lands[nx][ny] == 0: # 갈 수 없는 땅 체크
                    visited[nx][ny] = 0
                elif lands[nx][ny] == 1: # 갈 수 있는 땅 체크
                    visited[nx][ny] = visited[x][y] + 1
                    queue.append((nx,ny))

for i in range(N):
    for j in range(M):
        if lands[i][j] == 2 and visited[i][j] == -1:
            bfs(i, j)

for i in range(N):
    for j in range(M):
        if lands[i][j] == 0:
            print(0, end=' ')
        else:
            print(visited[i][j], end=' ')
    print()

• 위 문제와 마찬가지로 그래프랑 연관은 모르겠지만...BFS로 푸는 문제
• BFS로 풀면서 visited 리스트에 목표지점과의 거리를 저장한다. BFS는 목표지점부터 시작한다.

 

---

# 회고

 

그래프 자체 문제보다는 그래프를 응용한 문제들이여서 풀이를 생각해내기 어려웠다.

BFS, DFS를 다시 복습하는 것이 좋을 듯 하다..!