[백준] 2150 Strongly Connected Component, python
https://www.acmicpc.net/problem/2150 SCC란 u, v에 대해 u → v, v → u로 가는 경로가 모두 존재하는 최대 정점 집합이다. 즉 양방향으로 고리처럼 연결된 하나의 덩어리 같은 거다. 강한 연결 요소(SCC), 코사라주(Kosaraju) 알고리즘, python 강한 연결 요소(SCC), 코사라주(Kosaraju) 알고리즘, python강한 연결 요소란? 강한 연결 요소, SCC(Strongly connected component)란 방향이 있는 그래프의 정점 u, v에서 u → v, v → u로 가는 경로가 모두 존재하는 최대 정점 집합이다. 즉 양방향으로 연결된 하나의aiden0413.tistory.com 코사라주 알고리즘이란 dfs를 2번 돌면서 그래프..
[백준] 1700 멀티탭 스케줄링, python
https://www.acmicpc.net/problem/1700 각 전기용품이 사용되는 순서 인덱스를 저장한다.순서가 2, 3, 2, 3, 1, 2, 7이면1은 4에, 2는 0,2,5에, 3은 1,3에 7은 6에 등장하므로 해당 인덱스들을 저장한다플러그 딕셔너리를 생성한다. key=전기용품종류, value=사용되는 순서(배열의 인덱스)로 저장된다.플러그가 비어있다면 전기용품을 꽂고 딕셔너리에 추가하고, 사용 중인 전기용품이면 딕셔너리 인덱스를 늘린다.딕셔너리에 없는 전기용품을 사용할때 현재 사용순서로부터 사용순서가 제일 멀리 떨어진 전기용품을 뽑는다.전기용품사용되는 순서플러그 딕셔너리설명20{2:0}딕셔너리가 비어있으므로 전기용품종류: 사용되는 순서를 넣는다.2:0 을 넣는다.31{2:0, 3:1}플러..
[백준] 1600 말이 되고픈 원숭이, python
https://www.acmicpc.net/problem/1600 bfs를 사용해 나이트 사용 횟수가 남아있으면 나이트방향과 동서남북 방향 둘 다 탐색하고, 나이트 사용 횟수가 없으면 동서남북 방향만 탐색해서 해결했다. import sysfrom collections import dequeinput = sys.stdin.readlinek = int(input())w, h = list(map(int, input().split()))board = [list(map(int, input().split())) for _ in range(h)]dx = [0,0,1,-1] dy = [1,-1,0,0]horsex = [-1,-2,-2,-1,1,2,2,1]horsey = [-2,-1,1,2,2,1,-1,-2]vis..