본문 바로가기

Algorithm/Graph188

[파이썬] 백준 9466 : 팀 프로젝트 (골드3) [파이썬] 백준 9466 : 팀 프로젝트 (골드3)풀이방향성 생각DAG에서 사이클을 탐지하는 문제.SCC로 사이클을 탐지하는 타잔 알고리즘 사용자기 자신을 가르키는 간선은 제외해주고, scc를 구한 후 크기가 1인 scc만 자기 자신을 가르키는지 체크해주면 된다.코드import syssys.setrecursionlimit(10**6)input = lambda : sys.stdin.readline().strip()TC = int(input())for _ in range(TC): N = int(input()) arr = list(map(lambda x : int(x)-1,input().split())) G = [[] for _ in range(N)] for a,b in enumerate.. 2025. 5. 11.
[파이썬] 백준 27211 : 도넛 행성 (골드5) [파이썬] 백준 27211 : 도넛 행성 (골드5)백준 27211 : 도넛 행성 (골드5)풀이방향성 생각영역의 개수를 BFS/DFS로 세주기.영역 범위를 벗어나면 %연산을 통해서 영역 내부로 처리해주기.파이썬from collections import dequeimport sysinput = sys.stdin.readlinedires = [(1,0),(0,1),(-1,0),(0,-1)]H,W = map(int,input().split())arr = [list(map(int,input().split())) for _ in range(H)]V = [[False]*W for _ in range(H)]def bfs(x,y): V[y][x] = True Q = deque([(x,y)]) while .. 2025. 4. 24.
[파이썬] 백준 1175 : 배달 (골드1) [파이썬] 백준 1175 : 배달 (골드1)백준 1175 : 배달 (골드1)풀이방향성 생각비트마스킹 + 상태관리 BFS배달 완료한거는 비트마스킹으로, 이전 방향까지 고려해서 4차원 BFS 사용하기.혹은, C1 -> C2 / C2 -> C1 중 최소값을 고려해도 풀릴 듯 한데, 예외처리가 필요해보인다. (S.C.C 같은 경우)전체코드from collections import dequeimport sysinput = lambda : sys.stdin.readline().strip()inside = lambda x,y : 0코멘트. 쉬운문제 2025. 4. 24.
[파이썬] 백준 11281 : 2-SAT - 4 (플레3) [파이썬] 백준 11281 : 2-SAT - 4 (플레3)https://www.acmicpc.net/problem/11281풀이방향성 생각2 SAT 기본 문제 + 명제 추정하기입력이 들어오면 음수 노드를 양수로 만들어서 매핑해준다.풀고 알았는데, 보통 짝수를 참, 홀수를 거짓으로 매핑해서 각 node 0을 새로운 new node 0,1로 매핑한다.명제가 들어오면 전처리 이후, 대우 명제와 함께 그래프에 넣어주기.한 SCC 내에 x와 ~x가 같이 존재하면 모순이므로 명제를 참으로 만들 수 없다.모순이 발생하지 않으면 진입 차수가 낮은 노드부터 false를 매겨주고, 그 node의 부정은 true를 매겨준다. 전체코드import syssys.setrecursionlimit(10**6)input = lambd.. 2025. 4. 16.

티스토리툴바