[백준] 1613번 역사
-
문제 : 백준 1613번 역사
-
틀린 풀이 : 위상 정렬, DFS
- 각 노드를 정렬 (위상 정렬)
- 연결되지 않은 노드 분리 (DFS)
- 연결된 노드일 경우 정렬된 리스트에서 인덱스 비교하여 1 또는 -1 출력
- 연결되지 않았을 경우 0 출력
-
틀린 이유 : 연결되어 있지만 관계를 모르는 경우가 존재
-
맞은 풀이 : Floyd-Warshall, DP
- 2차원 거리 리스트 초기화
- 리스트[k][i][j] : 1부터 k까지의 노드만을 지나 i에서 j까지 도달하는 거리
- 모든 노드 간 거리 계산(N^2)을 N번 반복(3중 for문)
- 계산법 : 리스트[i][j] = min(리스트[i][j], 리스트[i][k]+리스트[k][j])
- 평가하려는 출발지로부터 도착지까지 도달할 수 없으면 거리 무한대
-
정리
-
굳이 거리를 계산할 필요 없을 것 같아 bool 타입으로 바꿔보았다
-
Floyd-Warshall 알고리즘
- O(N^3)
- 3차원 배열을 사용하지 않아도 되는 이유는 이해하기 조금 어렵다
- all-to-all 최단 경로 알고리즘
- one-to-one 또는 one-to-all : 벨만-포드, 다익스트라 알고리즘
-
다익스트라 알고리즘(N^2)을 모든 노드에 적용한 것(N)과 시간 복잡도 면에서 유사
-
틀린 코드
import sys, bisect
def init():
n, k = map(int, sys.stdin.readline().rstrip().split(' '))
order_list = []
directed_list = [[] for _ in range(n+1)]
undirected_list = [[] for _ in range(n+1)]
for i in range(k):
start, end = map(int, sys.stdin.readline().rstrip().split(' '))
order_list.append((start, end))
directed_list[start].append(end)
undirected_list[start].append(end)
undirected_list[end].append(start)
s = int(sys.stdin.readline().rstrip())
pair_list = []
for i in range(s):
start, end = map(int, sys.stdin.readline().rstrip().split(' '))
pair_list.append((start, end))
part_list = [0 for _ in range(n+1)]
index_list = [-1 for _ in range(n+1)]
sorted_list = []
return n, k, order_list, s, pair_list, part_list, undirected_list, directed_list, sorted_list, index_list
def dfs_ts(visited, curr_num):
visited[curr_num] = True
for next_num in directed_list[curr_num]:
if not visited[next_num]:
dfs_ts(visited, next_num)
sorted_list.append(curr_num)
index_list[curr_num] = len(sorted_list) - 1
def set_sorted_list():
visited = [False for i in range(n+1)]
for i in range(1, n+1):
if not visited[i]:
dfs_ts(visited, i)
def dfs(curr_num, part):
part_list[curr_num] = part
for next_num in undirected_list[curr_num]:
if part_list[next_num] == 0:
dfs(next_num, part)
def set_part_list():
part = 1
for i in range(1, n+1):
if part_list[i] == 0:
dfs(i, part)
part += 1
def check(pair):
start, end = pair
if part_list[start] == part_list[end]:
if index_list[start] < index_list[end]:
return 1
else:
return -1
else:
return 0
n, k, order_list, s, pair_list, part_list, undirected_list, directed_list, sorted_list, index_list = init()
set_sorted_list()
set_part_list()
for pair in pair_list:
sys.stdout.write(f'{check(pair)}\n')
맞은 코드
import sys
def init():
n, k = map(int, sys.stdin.readline().rstrip().split(' '))
order_list = [tuple(map(int, sys.stdin.readline().rstrip().split(' '))) for _ in range(k)]
s = int(sys.stdin.readline().rstrip())
pair_list = [tuple(map(int, sys.stdin.readline().rstrip().split(' '))) for _ in range(s)]
# dist_list = [[float('inf') for _ in range(n+1)] for _ in range(n+1)]
dist_list = [[False for _ in range(n+1)] for _ in range(n+1)]
return n, k, order_list, s, pair_list, dist_list
n, k, order_list, s, pair_list, dist_list = init()
for start, end in order_list:
# dist_list[start][end] = 1
dist_list[start][end] = True
for k in range(1, n+1):
for i in range(1, n+1):
for j in range(1, n+1):
# dist_list[i][j] = min(dist_list[i][j], dist_list[i][k]+dist_list[k][j])
dist_list[i][j] = dist_list[i][j] or (dist_list[i][k] and dist_list[k][j])
for start, end in pair_list:
# if dist_list[start][end] == float('inf') and dist_list[end][start] == float('inf'):
# sys.stdout.write('0\n')
# elif dist_list[start][end] == float('inf'):
# sys.stdout.write('1\n')
# elif dist_list[end][start] == float('inf'):
# sys.stdout.write('-1\n')
if not dist_list[start][end] and not dist_list[end][start]:
sys.stdout.write('0\n')
elif not dist_list[start][end]:
sys.stdout.write('1\n')
elif not dist_list[end][start]:
sys.stdout.write('-1\n')
Author And Source
이 문제에 관하여([백준] 1613번 역사), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다
https://velog.io/@leehj8896/백준-1613번-역사
저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)
import sys, bisect
def init():
n, k = map(int, sys.stdin.readline().rstrip().split(' '))
order_list = []
directed_list = [[] for _ in range(n+1)]
undirected_list = [[] for _ in range(n+1)]
for i in range(k):
start, end = map(int, sys.stdin.readline().rstrip().split(' '))
order_list.append((start, end))
directed_list[start].append(end)
undirected_list[start].append(end)
undirected_list[end].append(start)
s = int(sys.stdin.readline().rstrip())
pair_list = []
for i in range(s):
start, end = map(int, sys.stdin.readline().rstrip().split(' '))
pair_list.append((start, end))
part_list = [0 for _ in range(n+1)]
index_list = [-1 for _ in range(n+1)]
sorted_list = []
return n, k, order_list, s, pair_list, part_list, undirected_list, directed_list, sorted_list, index_list
def dfs_ts(visited, curr_num):
visited[curr_num] = True
for next_num in directed_list[curr_num]:
if not visited[next_num]:
dfs_ts(visited, next_num)
sorted_list.append(curr_num)
index_list[curr_num] = len(sorted_list) - 1
def set_sorted_list():
visited = [False for i in range(n+1)]
for i in range(1, n+1):
if not visited[i]:
dfs_ts(visited, i)
def dfs(curr_num, part):
part_list[curr_num] = part
for next_num in undirected_list[curr_num]:
if part_list[next_num] == 0:
dfs(next_num, part)
def set_part_list():
part = 1
for i in range(1, n+1):
if part_list[i] == 0:
dfs(i, part)
part += 1
def check(pair):
start, end = pair
if part_list[start] == part_list[end]:
if index_list[start] < index_list[end]:
return 1
else:
return -1
else:
return 0
n, k, order_list, s, pair_list, part_list, undirected_list, directed_list, sorted_list, index_list = init()
set_sorted_list()
set_part_list()
for pair in pair_list:
sys.stdout.write(f'{check(pair)}\n')
import sys
def init():
n, k = map(int, sys.stdin.readline().rstrip().split(' '))
order_list = [tuple(map(int, sys.stdin.readline().rstrip().split(' '))) for _ in range(k)]
s = int(sys.stdin.readline().rstrip())
pair_list = [tuple(map(int, sys.stdin.readline().rstrip().split(' '))) for _ in range(s)]
# dist_list = [[float('inf') for _ in range(n+1)] for _ in range(n+1)]
dist_list = [[False for _ in range(n+1)] for _ in range(n+1)]
return n, k, order_list, s, pair_list, dist_list
n, k, order_list, s, pair_list, dist_list = init()
for start, end in order_list:
# dist_list[start][end] = 1
dist_list[start][end] = True
for k in range(1, n+1):
for i in range(1, n+1):
for j in range(1, n+1):
# dist_list[i][j] = min(dist_list[i][j], dist_list[i][k]+dist_list[k][j])
dist_list[i][j] = dist_list[i][j] or (dist_list[i][k] and dist_list[k][j])
for start, end in pair_list:
# if dist_list[start][end] == float('inf') and dist_list[end][start] == float('inf'):
# sys.stdout.write('0\n')
# elif dist_list[start][end] == float('inf'):
# sys.stdout.write('1\n')
# elif dist_list[end][start] == float('inf'):
# sys.stdout.write('-1\n')
if not dist_list[start][end] and not dist_list[end][start]:
sys.stdout.write('0\n')
elif not dist_list[start][end]:
sys.stdout.write('1\n')
elif not dist_list[end][start]:
sys.stdout.write('-1\n')
Author And Source
이 문제에 관하여([백준] 1613번 역사), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@leehj8896/백준-1613번-역사저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)