본문 바로가기

Algorithm/Graph188

[파이썬] 백준 14719 : 빗물 (골드5) [파이썬] 백준 14719 : 빗물 (골드5)https://www.acmicpc.net/problem/빗물풀이방향성 생각왼쪽 벽이 아닌 높이에서 출발해서 같은 높이의 벽을 세워준다.마찬가지로 오른쪽 벽이 아닌 높이에서 출발해서 같은 높이의 벽을 세워준다.그 이상의 높이들은 비가 안오므로 그냥 1로 처리해주기이후 BFS 진행해서 남은 영역 넓이 구하기나는 그냥 입력받기 쉽게 그냥 회전시켜서 풀었다. 파이썬from collections import dequeimport sysinput = lambda : sys.stdin.readline().rstrip()inside = lambda x,y : 0테케 받아서 BFS 돌리기import sysinput = sys.stdin.readlineH, W = map(in.. 2025. 3. 17.
[파이썬] 백준 19701 : 소 운전한다 (골드1) [파이썬] 백준 19701 : 소 운전한다 (골드1)https://www.acmicpc.net/problem/19701풀이방향성 생각방문처리 배열 V에 돈까쓰를 먹은 유무를 추가해서 방문처리 관리하기 파이썬import heapq as hqimport sysinput = sys.stdin.readlineINF = float('inf')N,M = map(int,input().split())# 간선 정보 받아주기G = [[] for _ in range(N+1)]for _ in range(M): a,b,cost,flavor = map(int,input().split()) G[a].append((b,cost,flavor)) G[b].append((a,cost,flavor))# 방문처리 배열열V =.. 2025. 3. 12.
[파이썬,자바] 백준 13232 : Domain clusters (플레5) [파이썬,자바] 백준 13232 : Domain clusters (플레5)https://www.acmicpc.net/problem/13232풀이방향성 생각SCC의 컴포넌트 중 가장 사이즈가 큰 scc의 사이즈를 출력하면 된다.타잔이나 코사라주 아무거나 써서 scc 컴포넌트 구하고 크기 출력하기. 전체코드from collections import dequeimport syssys.setrecursionlimit(10**6)input = lambda : sys.stdin.readline().strip()N = int(input())M = int(input())G = [[] for _ in range(N+1)]for _ in range(M): a,b = map(int,input().split()) .. 2025. 3. 10.
[파이썬] 백준 15783 : 세진 바이러스 (플레4) [파이썬] 백준 15783 : 세진 바이러스 (플레4)https://www.acmicpc.net/problem/15783풀이방향성 생각타잔 알고리즘에서 구한 SCC 결과에서 진입차수가 0인 scc를 구해주면 된다.0-base인지 1-base인지 확인해주기 전체코드from collections import dequeimport syssys.setrecursionlimit(10**6)input = lambda : sys.stdin.readline().strip()N,M = map(int,input().split())G = [[] for _ in range(N+1)]for _ in range(M): a,b = map(int,input().split()) G[a].append(b)# 방문, 그룹관리 .. 2025. 3. 10.

티스토리툴바