미소를뿌리는감자의 코딩

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'를 반환시켜 ..

1. 문제https://www.acmicpc.net/problem/2665 2. 접근 방법미로 만들기는 0-1 BFS를 적용할 수 있는 문제였다.0-1 BFS에 알지 못했기에 이에 대해서 공부할 수 있던 좋은 기회였다. 실상은 BFS 보단 0-1, Dijkstra로 부르는 것이 더... 나을지도..?!라는 생각이 들었다.어떤 블로그에서 보았듯, 99% Dijkstra 에 1% BFS가 들어간 느낌이다.https://velog.io/@vkdldjvkdnj/boj01261 [BOJ 1261] - 알고스팟 (0-1 BFS, Python)BOJ 1261 - 알고스팟 (0-1 BFS, Python)velog.io 0-1 BFS에 대해서 이해할 때, 위 블로그가 도움이 많이 되었다. Dijkstra의 경우, lis..