Algorithm475 [파이썬] 백준 2150 : Strongly Connected Component (플레5) [파이썬] 백준 2150 : Strongly Connected Component (플레5)https://www.acmicpc.net/problem/2150풀이방향성 생각타잔 알고리즘. 그래프의 사이클 탐색하기 전체코드import syssys.setrecursionlimit(10**6)input = lambda : sys.stdin.readline().rstrip()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)cnt = 0V = [-1]*(N+1)P = [-1]*(N+1)on_stack = [False]*(N+1)stack .. 2025. 3. 7. [파이썬] 백준 16475 : 수학 미로 (골드1) [파이썬] 백준 16475 : 수학 미로 (골드1)https://www.acmicpc.net/problem/16475풀이방향성 생각2021 카카오 채용연계형 인턴십랑 비슷한 문제위 문제는 비트마스킹으로 변하는 간선을 관리했다면, 현재 문제는 단순 cycle을 통해서 문제 풀이.정방향 간선이랑 역방향 간선이 들어오는데, 정방향은 항상 탐색할 수 있고, 역방향인 경우 간선이 뒤집혔는지 유무에 따라서 체크해야한다.역방향 간선은 상태를 체크할 수 있는 변수를 추가해서 정방향 / 역방향으로 모두 넣어준다. 전체코드import sysimport heapq as hqinput = lambda : sys.stdin.readline().strip()INF = float('inf')N,M,K,L,P = map(int,in.. 2025. 3. 7. [파이썬] 백준 22956 : 소나기 (골드1) [파이썬] 백준 22956 : 소나기 (골드1)https://www.acmicpc.net/problem/22956풀이방향성 생각일단 쉬운 유니온파인드 문제랑 다르게, 유니온만 진행하는게 아니라 다른 정보들도 전달해줘야한다.일단 parent 배열을 1차원으로 축소해준다.parent에 x를 넣으면, 그 군집에 번호가 가장 작은 쪽으로 루트를 고정시켜준다. (일관된 기준만 있으면 달라도 상관 x)이에 맞추어서 infos에 x의 부모인 px를 넣으면, 그 군집의 루트에 해당 지역에서 가장 낮은 높이, 비가 온 마지막 날짜, 루트의 위치를 저장한다.union + 정보전달이 필요한 문제 파이썬import sysinput = lambda: sys.stdin.readline().strip()inside = lambda.. 2025. 3. 6. [파이썬] 백준 30894 : 유령의 집 탈출하기 (골드1) [파이썬] 백준 30894 : 유령의 집 탈출하기 (골드1)https://www.acmicpc.net/problem/30894풀이방향성 생각맵 정보를 입력받고, 시간에 따른 이동 가능/불가능 배열을 만든다.이동할 때 마다 유령기준으로 체크를 하면 cost가 커보인다.ban[mod][y][x]로 mod = t%4로 설정해서 각 시간대에 해당 위치가 접근 가능한지 저장한다.나머지는 BFS랑 비슷하게 풀 수 있다.제자리 구현이 있어서 TLE만 없다면 다익으로도 풀 수 있다.아마 TLE도 안날듯?제자리를 구현할 때, 해당 방향으로 이동 시 기다려야하면 기다리는 시간을 같이 더해주면 된다.사실 BFS로 이런 방식으로 풀 수 있는데, cur_time이라는 변수를 하나 두고 시간이 cut_time과 0 또는 1차이가.. 2025. 3. 3. 이전 1 ··· 21 22 23 24 25 26 27 ··· 119 다음
