전체 글623 [파이썬] 백준 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. [파이썬] 백준 18128 : 치삼이의 징검다리 건너기 (골드1) [파이썬] 백준 18128 : 치삼이의 징검다리 건너기 (골드1)https://www.acmicpc.net/problem/18128풀이방향성 생각시작 / 도착 위치는 항상 밟을 수 있다는 예외처리하기.BFS로 물이 퍼져나가는 시간을 구한다.fountains에 water src를 받아놓고, flood에 물이 퍼진 시간을 기록한다.이후, 다익스트라를 사용해서 (t,x,y)를 힙에 넣는다.t는 현재가지 가장 작은 flood를 갱신하면서 힙에 넣는다. 파이썬from collections import dequeimport sysimport heapq as hqinput = lambda : sys.stdin.readline().strip()inside = lambda x,y: 0 V[y][x]: con.. 2025. 3. 3. 이전 1 2 3 4 5 6 7 8 ··· 156 다음
