목록2024/09 (49)
미소를뿌리는감자의 코딩
1. 문제https://www.acmicpc.net/problem/2637 2. 접근 방법이번 문제는 정석적인 위상 정렬에서, 개수가 포함된 문제이다. part_need라는 2차원 리스트를 구성하고, 이를 통해서 위상 정렬 동안 계산이 되는 결과를 저장해 주었다.inDegree가 없는 것부터 접근하여, 마지막까지 계산을 진행하기 때문에, 필요한 부품에 대한 정보가 순차적으로 저장이 되게 된다. 만약 5번 부품이 2번 부품 3개를 필요로 하게 된다면 2번 행에 * 3을 한 idx 값을 5번 행에 더해주었다. 3. 코드from collections import dequefrom collections import defaultdictdef machine(): dq = deque() base = []..
1. 문제https://www.acmicpc.net/problem/2252 2. 접근 방법위상 정렬을 사용하도록 하는 문제였다.키의 순서를 adj에 정렬해 주고, inD라는 함수에 몇개의 진입 차수를 필요로 하는지 표현해 주었다. 3. 코드from collections import dequedef topological(): queue = deque() result = [] for i in range(1, num+1, 1): if inD[i] == 0: queue.append(i) for _ in range(num): if not queue: return -1 q = queue.popleft() ..
1. 문제https://www.acmicpc.net/problem/22942. 접근 방법처음에는 bfs를 이용해서 coin의 개수를 1개씩 늘려가면서, 만약 합이 k인 경우가 나온다면, 이를 반환하는 코드를 작성했었다.이런식으로 bfs 코드를 구상하고 작성하였다. from collections import dequedef get_min_coin(): c_cnt = 0 visited = [] while bfs: c_cnt += 1 coin_length = len(bfs) for _ in range(coin_length): coin_popped = bfs.popleft() if coin_popped in visite..
1. 문제https://www.acmicpc.net/problem/30552. 접근 방법2개의 BFS를 이용해서 문제를 해결할 수 있었다. 처음에 지도에 대한 상태를 input으로 받아들이면서, 'S'와 '*'에 대한 정보를 받아들였다. water에 대한 deque를 만든 후, 물이 퍼져나감에 따라 '.'을 '*'로 고쳐주었다. 물론 범위 안에 있는 지 유무를 확인하였다. 고슴도치의 위치 또한 hedge라는 deque에 넣어준 후, 시간이 지남에 따라 위, 아래, 왼쪽, 위로 이동시켜주었다. 이 또한 범위 안에 있는지, 그리고 이동하고자 하는 곳이 '.' 인지 확인하여 주었다. 탈출 조건으로는, 만약 hedge의 length가 0일 경우엔, 이동할 수 있는 곳이 없는 것이므로 'KAKTUS'를 반환시켜 ..