Coding 공부

import collections
 
 
def bfs(i):
    global N,graph,result
    stack = collections.deque()
    stack.append((i,0))
    visited = [True] * (N+1)
    visited[i] = False
    while stack:
        ind,dep = stack.popleft()
        for next_ind in graph[ind]:
            if visited[next_ind]:
                stack.append((next_ind,dep+1))
                visited[next_ind] = False
    return dep
 
 
 
 
 
 
 
N = int(input())
graph = [[] for _ in range(N+1)] 
while True:
    a,b = map(int,input().split())
    if a == -1 and b == -1:
        break
    graph[a].append(b)
    graph[b].append(a)
 
 
result = [50]*(N+1)
for i in range(1,N+1):
    result[i] = bfs(i)
 
 
min_list = [min(result),result.count(min(result))]
print(*min_list)
min_result = []
for i in range(1,N+1):
    if result[i] == min_list[0]:
        min_result.append(i)
print(*min_result)

 친구의 깊이를 물어보는 문제였다. 문제에서 들어오는 최대 인원이 50이므로 50으로 해놓은 상태에서 바꿨다.

그리고 깊이를 물어보는 것이기 때문에, DFS가 아닌 BFS를 이용해서 최단거리를 깊이로 생각해서 풀었다.

# 플로이드 와샬
 
N = int(input())
graph = [[0]+[50]*N if i!=0 else [50]*(N+1) for i in range(N+1)]
while True:
    a,b = map(int,input().split())
    if a == b == -1:
        break
    graph[a][b] = 1
    graph[b][a] = 1
 
for i in range(1,N+1):
    graph[i][i] = 0
 
for k in range(1,N+1):
    for from_node in range(1,N+1):
        for to_node in range(1,N+1):
            if graph[from_node][to_node] == 1 or graph[from_node][to_node] == 0:
                continue
            elif graph[from_node][to_node] > graph[from_node][k] + graph[k][to_node]:
                graph[from_node][to_node] = graph[from_node][k] + graph[k][to_node]
 
 
min_result = list(map(max,graph))
 
print(min(min_result),min_result.count(min(min_result)))
min_ind = []
for ind,val in enumerate(min_result):
    if val == min(min_result):
        min_ind.append(ind)
print(*min_ind)

플로이드 와샬 방식으로 푼 방식이다.

기본 원리는 같지만 연결을 표현한 방식이 달라졌을 뿐이다.

# 11403 경로 찾기
 
 
 
N = int(input())
arr = [list(map(int,input().split())) for _ in range(N)]
for k in range(N):
    for x in range(N):
        for y in range(N):
            if arr[x][k] + arr[k][y] == 2:
                arr[x][y] = 1
 
for i in range(N):
    print(*arr[i])

풀고보니 플로이드 와샬 문제였다.

중간 경로를 통해서 두개가 연결이 되는 경우 arr를 갱신해주는 방식으로 했다.

이 방식 말고도 BFS,DFS를 통해 node들을 탐색해서 푸는 방식도 있다.