코딩테스트 대비 백준 문제 뽀개기 : 준비운동 PART2. 약점 체크

0. 문제 출처

https://covenant.tistory.com/224?category=727170 

코딩테스트 대비를 위한 백준 문제 추천

 

1. 연산자 끼워넣기

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

14888번: 연산자 끼워넣기

- N개의 수로 이루어진 수열이 주어지고, 수 사이에 끼워넣을 수 있는 N-1개의 연산자가 주어질 때 만들 수 있는 최대값과 최소값을 출력

- 리스트에 리스트 추가 : arr.extend(리스트)
- 조합 만들 때 중복 데이터가 있을 때 => permutation결과값을 set에 저장하고 다시 list로 만들기 

 

(코드)

from itertools import permutations

def caculate_num(arr,op):
	result = arr[0]

	for idx in range(N-1):
		if op[idx] == '+':
			result += arr[idx+1]
		elif op[idx] == '-':
			result -= arr[idx+1]
		elif op[idx] == '*':
			result *= arr[idx+1]
		else:
			if result < 0 and arr[idx+1] > 0:
				result = -( abs(result) // arr[idx+1])
			else:
				result //= arr[idx+1]
	return result 
		
def solution(arr,oper):
	N = len(arr)
	answer = []
	min_num = 1000000000
	max_num = -1000000000

	op_list = [ '+' for _ in range( oper[0] ) ]
	op_list.extend( list('-' for _ in range(oper[1])))
	op_list.extend( list( '*' for _ in range(oper[2])))
	op_list.extend( list('//' for _ in range(oper[3])))

	#op_list에서 나올 수 있는 경우의 수대로 값을 구하기 
	for op in set(permutations(op_list, N-1)):
		tmp = caculate_num(arr,op)
		min_num = min(tmp,min_num)
		max_num = max(tmp,max_num) 
			
	answer.append(max_num)
	answer.append(min_num)
	return answer

if __name__ == "__main__":
	N = int(input())
	arr = list(map(int,input().split(" ")))
	oper = list(map(int,input().split(" ")))

	answer = solution(arr,oper)
	for x in answer:
		print(x)

- dfs로 풀기: 가능한 plus횟수,minus횟수,multiply횟수,divide횟수를 dfs의 변수로 저장하고 각 값이 0보다 크면 해당 연산 수행하기

- 아주 중요한 것!!! 전역변수로 선언(혹은 main함수에서 선언)하더라도 함수에서 해당 변수 / 리스트를 global 없이 사용하면 그건 지역변수가 된다!!!!그래서 다른 함수에서 전역 변수 사용하려하면 에러남!!!!!반드시 전역 변수/리스트는 global 키워드 쓰고 사용할것!!!!!!!!!!!!!!!!!!11

#dfs로 풀기 

numlist = []
max_value = -1000000000
min_value = 1000000000

def dfs(idx,value,plus,minus,multi,divid):
	if idx == N:
		global max_value, min_value
		max_value = max(max_value, value)
		min_value = min(min_value, value)
		return
	else:
		global numlist
		if plus > 0:
			dfs(idx+1,value + numlist[idx],plus-1,minus,multi,divid)
		if minus > 0:
			dfs(idx+1,value - numlist[idx],plus,minus-1,multi,divid)
		if multi > 0:
			dfs(idx+1,value * numlist[idx],plus,minus,multi-1,divid)
		if divid > 0:
			val = 0
			if value < 0 and numlist[idx] > 0:
				val = -( abs(value) // numlist[idx] )
			else:
			 	val = value // numlist[idx]
			dfs(idx+1,val,plus,minus,multi,divid-1)
	

def solution(arr,op_list):
	N = len(arr)
	global numlist
	numlist = arr.copy()
	plus, minus, multi, divid =  op_list[0], op_list[1],op_list[2],op_list[3]
	dfs(1,numlist[0],plus,minus,multi,divid)


if __name__ == "__main__":
	N = int(input())
	arr = list(map(int,input().split(" ")))
	op_list = list(map(int,input().split(" ")))

	solution(arr,op_list)
	print(max_value)
	print(min_value)

 

 

--------------------------------------------------------------------------------------

2. [2504] 괄호의 값( 스택 )

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

2504번: 괄호의 값

- 가장 안쪽 ():2, 가장 안쪽 []:3, (x) : 2*x, [x] : 3*x, xy = x+y 일때 올바른 괄호인 경우 괄호값의 합 구하기 

- python의 stack은 deque 쓰고, append(), pop()함수 사용! top은 없음

- stack에서 인덱스 접근(top 포함) 시 항상!!! len(s) != 0 인지 확인하는게 정신건강과 런타임에러에 좋음ㅎ 

- stack에 괄호열만 넣지 말고 값을 넣을 수 있음!!!! 단 stack에 값 넣을때 str()로 넣어야 나중에 stack에서 꺼낼 때 숫자인 경우 isdigit()를 확인할 수 있음!!!!!

(ex.  ( [] () [[]] ) = ( 3, 2, 9) = (3+2+9) *2로 계산할 수 있음

- stack을 이용한 괄호 문제는 항상 다 넣고나서 stack에 값이 있는지 확인할 것!!!!

(코드)

from collections import deque

def solution( st ):
	answer = 0
	s = deque() #stack

	for i in range(len(st)):
		x = st[i]
		if x == '(' or x == '[':
			s.append(x)

		elif x == ')':
			tmp = 0
			if len(s) == 0 or s[-1] == '[':
				return 0
			elif s[-1] == '(':
				tmp = 1
            #숫자가 있으면, '(' 가 나올때까지 숫자들을 더함
			else:
				tmp = int(s.pop())
				while len(s) != 0 and s[-1].isdigit() == True:
					tmp += int(s.pop())
				if len(s) == 0 or s[-1] == '[':
					return 0
			s.pop()
			s.append(str(tmp*2))

		elif x == ']':
			tmp = 0
			if len(s) == 0 or s[-1] == '(':
				return 0
			elif s[-1] == '[':
				tmp = 1
			else:
                #숫자가 있으면 '['가 나올 때까지 숫자들 더함 
				tmp = int(s.pop())
				while len(s) != 0 and s[-1].isdigit() == True:
					tmp += int(s.pop())
				if len(s) == 0 or s[-1] == '(':
					return 0
			s.pop()
			s.append(str(tmp*3))
	
	#stack에 괄호가 남아있는 경우 잘못된 괄호
	if len(s) == 0 :
		return 0
	elif  '(' in s or '[' in s:
		return 0

	answer = sum( list( int(x) for x in s) )
	return answer
		

if __name__ == "__main__":
	st = input()
	answer = solution(st)
	print(answer)

 

--------------------------------------------------------------------------------------

3. 빗물

- https://www.acmicpc.net/problem/14719

14719번: 빗물

- 투포인터 문제. 가장 큰 높이의 높이 & 인덱스를 찾고 왼쪽 -> 탑. 오른쪽 -> 탑까지 꾸준히 더해줌
- 조건 : 현재 위치보다 양쪽에 더 높은 블록이 존재하면 현재 위치에 빗물이 고인다. 
- 현재위치의 왼쪽 블록 중 가장 큰 높이(a), 현재위치의 오른쪽 블록 중 가장 큰 높이(b)를 찾고 min(a,b) - 현재 높이 값들을 더해나감. 단 현재 높이가 a,b보다 클 수 있으니 a,b의 초기값을 현재 높이로 설정하기!

 

( 코드)

def solution(H,W,arr):
	answer = 0 
	
	for i in range(1,W-1):
		left = max(arr[:i+1]) #현재 높이가 더 높을 수 있으므로 현재 높이까지 비교하기 
		right = max(arr[i:])
		answer += ( min(left,right) - arr[i] )
		
	return answer

if __name__ == "__main__":
	H,W = map(int,input().split(" "))	
	arr = list(map(int,input().split()))
	answer = solution(H,W,arr)
	print(answer)

 

--------------------------------------------------------------------------------------

4. 가르침

- https://www.acmicpc.net/problem/1062

1062번: 가르침

- 북극의 단어는 anta ~~~ tica의 규칙으로 만들어준다. K개의 알파벳을 가르칠 때 읽을 수 있는 단어의 수 중 최댓값?

- from itertools import combinations

- ord() : 알파벳 -> 아스키코드 // chr() : 아스키코드 -> 알파벳

- 리스트 삭제: remove(삭제할 값), pop(삭제할 인덱스)

- combination의 결과 쌍은 "tuple"단위로 저장됨!! combinations(arr,K) = [ (), (), (),... ]

- combination할 때 최소 경우의 수도 알아야 함! 조합 개수 > arr 개수인 경우 조합이 아예 안나온다!!!!! 이런 경우 min(K,len(arr))로 해야 함!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

-알파벳 리스트 만드는 법: from string import ascii_lowercase

- 시간초과 걱정되는 경우, 슬라이싱은 오래걸림!! slice[a:b] = O(b-a)(슬라이싱되는 요소 수만큼)

- list로 비교보다 set으로 계산하는게 빠름

- set끼리 덧셈, 뺄셈, 포함관계 비교 가능함 (set은 집합이므로)

( set(a), set(b) 후 if a<= b :는 A의 요소가 B에 포함되는지를 묻는 것임)

 

(코드)

from itertools import combinations

N, K = map(int,input().split())
except_char = set(['a','c','i','n','t'])
words = [ set(list(input())) - except_char for _ in range(N) ]
answer = 0

if K < 5:
	print(0)
	exit(0)

alpha = set( sum([ list(word) for word in words ], []) )
   
combs = combinations(alpha, min(len(alpha), K - 5))
for comb in combs:
	comb = set(comb)
	cnt = 0
	for word in words:
		if word <= comb:
			cnt += 1
	answer = max(answer, cnt)
print(answer)

 

--------------------------------------------------------------------------------------

5. 멀티탭 스케줄링 - 그리디 

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

1700번: 멀티탭 스케줄링

- 멀티탭의   구  개수가  주어지고, 전기용품을 사용하는 순서가  주어질때, 최소로  멀티탭을  뺄 수 있는 횟수 출력
# 완탐 안되는 이유 : N =2, K = 100일때 98번동안 둘 중에 하나를 뽑아야 하는 경우의 수로 2^98제 곱이 됨
# dp랑 그리디 중 선택해야 하는데 dp도 매 번 그 당시의 멀티탭 배열을 저장해야 함 -> 그럼 그리디 같다

- 리스트에서 특정 값의 첫번째 인덱스 출력 : arr.index(값)

- 리스트에서 특정 값의 모든 인덱스 저장 : result = [ idx for idx,value in enumerate(arr) if value == 값 ]

- 처음에 무조건 가장 마지막 인덱스를 뽑는건 줄 알았는데, 멀티탭에 있는 대상들이 이후에 다시 나온다면, 처음으로 나오는 위치가 제일 늦은 걸 찾는거임! ex) 2 4 3이 꽃혀있고 5를 넣어야 함. 그 다음 arr가 4 3 2라고 하면 2를 뽑아야 함. 그래야 5 4 3 -> 5 4 3 -> 2 4 3 으로 한번만 뽑을  수 있음

- 뭔든지 맨 처음에 값을 고정적으로 넣을떈 개수랑 제약조건 확인하는 습관 가지기!!! 항상 K < N를 만족하는건지, 만약 1 1 1 2 3 등으로 들어올 땐 어떻게 되는지 등등

 

 

(코드)

def	solution(N,K,arr):
	answer = 0
	if N >= K:
		return 0
	
	#처음 N개 멀티탭에 삽입
	multi_tap = []
	cnt = 0
	for start in range(K):
		if arr[start] not in multi_tap:
			multi_tap.append(arr[start])
			cnt += 1
			if cnt == N:
				break
	
	#N+1~K번째로 사용할 전기기구를 어디에 넣을지 선택 
	for i in range(start+1,K):
		#i번째로 사용할 기구가 이미 멀티탭에 있는 경우  
		if arr[i] in multi_tap:
			continue
		
		#멀티탭에 있는 대상 중 앞으로 다시 쓰이지 않는 대상 탐색 
		check_selected = False
		for mt in multi_tap:
			if mt not in arr[i+1:]:
				delete_idx = multi_tap.index(mt)
				multi_tap[delete_idx] = arr[i]
				check_selected =  True
				answer += 1
				break
		
		#멀티탭에 모든 대상이 이후에 다시 쓰이면, 가장 마지막으로 쓰이는 전기 기구를 뽑음
		if check_selected == False:
			max_idx = -1
			delete_idx = 0
			for mi in range(N):
				mt = multi_tap[mi]
				tmp_idx = arr[i+1:].index(mt)
				if max_idx < tmp_idx:
					max_idx = tmp_idx
					delete_idx = mi
		
			multi_tap[delete_idx] = arr[i]
			answer += 1

	return answer 


if	__name__ ==	"__main__":
	N,K	= map(int,input().split())
	arr	= list(map(int,input().split()))

	answer = solution(N,K,arr)
	print(answer)

 

--------------------------------------------------------------------------------------

6. 부분합 - 투포인터 ( 숙지할 것 )

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

1806번: 부분합

- 연속된 수들의 부분합 중에 그 합이 S 이상이 되는 것 중, 가장 짧은 것의 길이를 출력하라 

- 유의할 것 : right포인터는 값이 S이상인 부분합의 "마지막요소 + 1"의 인덱스이다!!! (합을 구하고 무조건 +1하므로). 따라서 길이를 구할 땐 +1하지 말고 right - left만 할 것

 

( 코드 )

#부분합이 S이상인 부분합 중 가장 짧은 부분합의 길이 출력 
MAX = 1000001

def solution(N,S,arr):
	answer = MAX
	left = right = 0
	interval_sum = 0
	
	while True:
        # 부분합이 S이상인 경우, 부분합 길이를 구한 후 left포인터 옮김 
		if interval_sum >= S:
			answer = min(answer, right-left)
			interval_sum -= arr[left]
			left += 1

		elif right == N:
			break
        # 부분합이 S미만인 경우 right포인터를 옮김 
		else:
			interval_sum += arr[right]
			right += 1

	if answer == MAX:
		answer = 0
	
	return answer

if __name__ == "__main__":
	N,S = map(int,input().split())
	arr = list(map(int,input().split()))

	answer = solution(N,S,arr)
	print(answer)

 

--------------------------------------------------------------------------------------

7. 최소비용 구하기 (다익스트라)

- https://www.acmicpc.net/problem/1916

1916번: 최소비용 구하기

- N개의 도시가 주어지고, 각 도시로 가는 버스와 비용이 주어질 때 A -> B도시로 가는 버스 비용의 최소비용 출력

- 특정 노드 -> 다른 노드 최단 거리 : 다익스트라. 모든 거리 : 플로이드 워셜(N^3)
- 우선순위 큐: from heapq import heappush, heappop  // 그냥 큐 : from collections import deque

- 최단거리에서 필요한 것: distance[], graph[a] = (b,c) # a ->b로가는 비용이 c

- 최단거리 구할땐 중간에 큐의 pop한게 도착노드라도 break하지 않음

- import sys, input = sys.stdin.readline() 사용하기!!!

 

(코드)

#최단거리 구할땐 중간에 큐의 pop한게 도착노드라도 break하지 않음
import sys
from heapq import heappush, heappop
INF = 100000001
input = sys.stdin.readline

def dijkstra(bus,start,end):
	hq = []
	distance = [INF] * (N+1)

	#시작노드를 큐에 삽입하고 최단 경로 구하기
	heappush(hq,(0,start)) #비용, 시작 노드
	distance[start] = 0

	while hq:
		dist,cur_node = heappop(hq)
	#이미 그 노드로 가는 최단경로를 구한 적이 있고, 그 거리가 큐에서 뽑은 거리보다 작은 경우 pass
		if distance[cur_node] < dist:
			continue
	# 아직 최단 경로를 구한 적이 없거나, 예전에 거리를 구했어도 지금 큐에서 뽑은 거리가 더 작은 경우. 인접 노드에 연결된 최단 거리도 update 
		else:
			if cur_node in bus:
				for adj_node in bus[cur_node]:
					cost = dist + adj_node[1]
					if cost < distance[adj_node[0]]:
						distance[adj_node[0]] = cost
						heappush(hq,(cost,adj_node[0]) )
	
	return distance[end]

if __name__ == "__main__":
	N = int(input())
	M = int(input())
	bus = {}
	#간선 정보 입력받기 
	for _ in range(M):
		a,b,c = map(int,input().split())
		
		if a not in bus:
			bus[a] = []
		bus[a].append( (b,c) )	
	
	start, end = map(int,input().split())

	answer = dijkstra(bus,start,end)
	print(answer)

 

--------------------------------------------------------------------------------------

8. 최소 스패닝 트리 (크루스칼, 프림)

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

1197번: 최소 스패닝 트리

- 최소 스패닝 트리(MST), 간선의 가중치가 최소인 스패닝 트리를 구현하라

- 크루스칼 : union-find 기반, 단 union하기 전에 find함수로 합치려는 두 원소의 부모가 같지 않은지만 확인하기

- 크루스칼 심화 구현은 여기 :https://www.fun-coding.org/Chapter20-kruskal-live.html  https://codingcocoon.tistory.com/131

 

( 크루스칼 코드)

# 최소 스패닝 트리, MST
# 최소스패닝 트리는 어차피 순서가 없으므로 a,b = c랑 b,a = c를 굳이 따로 저장할 필요 없음

#특정 원소가 속한 집합 찾기
#union-by-rank: 각 트리에 대해 높이를 기억. 두 트리의 높이가 다르면 높이가 작은 트리를 큰 트리에 붙임(높이가 큰 트리의 루트 노드가 합친 집합의 루트 노드가 되도록 함)
parent = []

def find(x):
    global parent
    if parent[x] == x:
        return x
    parent[x] = find(parent[x])
    return parent[x]

#두 원소가 속한 집합을 합치기 (간선을 연결)
def union(a,b):
    global parent 
    roota = find(a)
    rootb = find(b)
    
    if roota < rootb:
        parent[rootb] = roota 
    else:
        parent[roota] = rootb

#크루스칼 알고리즘 사용 	  
def solution(V,edges):
    answer = 0
    global parent
    parent = list( range(V+1) )#부모를 자기 자신으로 초기화 
    edges.sort() #비용순으로 오름차순 정렬

    #union 연산 수행
    for edge in edges:
        cost,a,b = edge
    #사이클이 발생하지 않는 경우--부모원소가 같지않은 경우-- 집합에 포함
        if find(a) != find(b):
            union(a,b)
            answer += cost
    return answer 


if __name__ == "__main__":
    V,E = map(int,input().split())
    edges = []

    for _ in range(E):
        a,b,c = map(int,input().split())
        edges.append( (c,a,b))
    
    answer = solution(V,edges)
    print(answer)

 

** 프림 **

- visited 배열 사용 

- heapq 사용 

- a->b cost가 주어지면 graph[a].append( (c,a,b) )와 graph[b].append( ( c,b,a) ) 으로 양방향으로 그래프를 넣어야 함

 

 

( 프림 코드)

#프림 알고리즘
#프림 알고리즘은 a -> b값이 주어지면  b->a값도 넣어야 함
# visited & 우선순위 큐 필요
#input = sys.stdin.readline

import heapq  #프림 
import sys
from collections import defaultdict #빈 리스트를 생성 
input = sys.stdin.readline

def solution(V,edges):
	mst = list() #최소신장트리
	visited = [False] * (V+1) #방문 확인 리스트
	answer = 0
#1번 노드부터 탐색시작
	visited[1] = True
	hq = edges[1] 
	heapq.heapify(hq) #1번 노드에 연결된 정보를 우선순위 큐로 바꿈

	while hq:
		cost,a,b = heapq.heappop(hq)
		#방문한 적이 없는 노드면 mst에 추가 
		if visited[b] == False:
			visited[b] = True
			mst.append( (a,b) )
			answer += cost
		#방금 추가한 노드의 간선 정보 추가 
			for edge in edges[b]:
				if visited[edge[2]] == False:
					heapq.heappush(hq,edge)
	return answer

if __name__ == "__main__":
    
	V,E = map(int,input().split())
	edges = defaultdict(list) #빈 그래프 생성 
	for _ in range(E):
		a,b,c = map(int,input().split())
		edges[a].append( [c,a,b] )
		edges[b].append( [c,b,a] )
	
	answer = solution(V,edges)
	print(answer)

 

--------------------------------------------------------------------------------------

8. 부분 문자열(KMP)

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

16916번: 부분 문자열

- 두 문자열 S,P가 주어질 때 P가 S에 포함되면 1,아니면 0 출력

- KMP 알고리즘.. 

https://injae-kim.github.io/dev/2020/07/23/all-about-kmp-algorithm.html

Injae's devlog

https://bowbowbow.tistory.com/6

KMP : 문자열 검색 알고리즘

 

(코드)

#16916 부분 문자열
#문자열 S,P가 주어질 때 P가 S의 부분 문자열이면 1 아니면 0을 출력하라
# KMP 알고리즘 :
# pi[i] : 0~i까지의 부분 문자열 중 prefix == suffix인 부분 문자열의 가장 긴 것의 길이 단, i < len(S) --> 이건 부분문자열에 대해 구하는것임!!!!! 
'''a
ABAABAB이라하면 ,
pi[0] : A = 0
pi[1] : AB = 0
pi[2] : ABA - 양 끝의 A가 같음 = 1
pi[3] : ABAA - 양 끝의 A가 같음 = 1
pi[4] : ABAAB - 양 끝의 AB가 같음 = 2
pi[5] : ABAABA - 양 끝의 ABA가 같음 = 3
'''
#kmp찾을 땐begin = matched = 0으로 시작함 

def get_partial_match(S):
	begin = 1
	matched = 0 #탐색할 prefix 문자 위치 겸, pre=suf인 부분 문자열의 길이 
	pi = [0] * (len(S))
#비교할 문자가 S의 끝에 도달할 때까지 부분일치 기록 
	while begin + matched < len(S):
	 	#S[matched]와 같은 글자가 S[begin+matched]위치에 존재하는 경우
		if S[begin + matched] == S[matched]:
			matched += 1
			pi[begin+matched-1] = matched 
           # begin+matched까지 부분 문자열은 matched길이로 prefix= subfix를 만족한다 
		else:
			#맨 처음글자와 일치하는 위치까지 begin++ 
			if matched == 0:
				begin += 1
			# 현재 불일치가 발생한 위치는 begin +matched
			# 매칭을 진행하면서 구했었던 접두/접미사 길이만큼 탐색을 건너뒬 수 있다. 
            # 접두/접미사 길이가 pi[matched-1]임 
			else:
				begin += matched - pi[matched-1]
				matched = pi[matched - 1]
	return pi

def kmp_search(S,P):
	answer = 0
	N = len(S)
	M = len(P)
	pi = get_partial_match(P)
	begin = matched = 0

	while begin <= (N-M) :
		#P[begin+matched]와 S[matched]가 동일할 경우 matched ++
		if matched < M and S[begin+matched] == P[matched]:
			matched += 1

		#문자열이 모두 일치함 
			if matched == M:
				answer = 1
				break

		else:
		 	#일치부분 없을 때 다음 문자부터 탐색 
			if matched == 0:
				begin += 1
			#문자열 불일치. 접두사, 접미사 길이만큼 건너 뀜
			else:
				#접두/접미사 길이인 pi[matched-1]을 빼주면 다음 탐색의 시작 위치. begin은 증가, 
                #matche는 감소
				begin += (matched - pi[matched-1])
				matched = pi[matched-1]
	return answer 

if __name__ == "__main__":
	S = input()
	P = input()
	answer = kmp_search(S,P)
	print(answer)

 

--------------------------------------------------------------------------------------

9. 줄 세우기(위상정렬)

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

2252번: 줄 세우기

- 일부 학생들의 키를 비교한 결과가 주어졌을 때( a 는 b보다 작다), 줄을 세우는 프로그램을 작성하라

- 위상정렬 특징 : 단방향 간선이 존재. (disjoint-set이랑 헷갈리지 말것. union-find기반 알고리즘은 순서가 필요 X)
- "visited","단방향 그래프", "진입 차수 리스트", "큐 " 가 필요
- 보통 그래프에선 자료구조를  연결리스트(2차원 리스트) 혹은 dictionary로 구현( 난 전자로 하자)

- 전체 알고리즘 

  1. 진입차수가 0인 노드를 큐에 넣는다.
  2. 큐가 빌 때까지 반복
    - 원소를 꺼내 해당 노드에서 출발하는 간선을 제거
    - 새롭게 진입차수가 0이 된 노드를 큐에 삽입
  3. 만약 모든 노드를 방문하기 전 큐가 닫히면 사이클인거임
  (근데 보통 위상정렬은 사이클 발생 안하도록 제시함)

 

- from collections import defaultdict 한 후에 arr= defaultdict(list) #빈 리스트 생성 

( 관련 블로그 글 :https://itholic.github.io/python-defaultdict/)
- 2차원 배열 입력받을 때 arr.append( [ map(int,input().split())]) 말고 arr.append( list(map(int,input())) )으로 해야 한다...
-리스트 출력 != 리스트 값 출력. 전자는 print(answer)하면 [ ]이 포함됨  

 

 

( 코드 )

from collections import deque, defaultdict 

def solution(N,arr):
	answer = []
	graph = defaultdict(list)
	indegree = [0] * (N+1)

	#위상정렬 그래프 생성 
	for ar in arr:
		a,b = ar
		graph[a].append(b) #리스트 이므로 [a] = b가 아니라 append
		
		indegree[b] += 1
	
	#위상정렬 수행
	q = deque()
	
	#진입차수가 0인 노드들 큐에 삽입
	for i in range(1, N+1):
		if indegree[i] == 0:
			q.append(i)
	
	while q:
		cur = q.popleft()
		answer.append(cur)
		# 해당 원소와 연결된 노드 진입차수들 -1하기 
		for i in graph[cur]:
			indegree[i] -= 1

		# 새롭게 진입 차수가 0 되는 노드를 큐에 삽입 
			if indegree[i] == 0:
				q.append(i)
			
	return answer


if __name__ == "__main__":
	N,M = map(int,input().split())
	arr = list()
	for _ in range(M):
		arr.append( list(map(int,input().split())))

	answer = solution(N,arr)
	for x in answer:
		print(x,end = " ")