문제https://www.acmicpc.net/problem/2573 해설BFS를 이용하여 해결할 수 있었다. melting, multipartite 검사, BFS로 각 스텝을 구성하였다. 녹는 빙하에 대해서는 loop를 줄이기 위해 BFS에서 녹아야 하는 빙하의 좌표를 미리 입력받았다. Pythonfrom sys import stdinfrom collections import dequecommand = [[-1, 0], [0, -1], [0, 1], [1, 0]]def bfs(graph: list, visited: list, start_x: int, start_y: int, melt_list: list): queue = deque() queue.append([start_x, start_y])..
문제https://www.acmicpc.net/problem/1707 해설DFS와 BFS 모두 사용가능한 문제이다. DFS를 이용하는 것이 개인적으로 이번 문제에선 이해가 잘 되었던 것 같다. PythonPython은 파이썬의 기본 재귀 깊이 제한은 1000이기 때문에 setrecursionlimit를 사용하지 않으면 런타임 에러가 발생한다. 너무 크게 설정해도 메모리 오류가 발생하므로 적절한 크기로 조절이 필요하였다. DFSfrom sys import stdin, setrecursionlimitsetrecursionlimit(100000)def dfs(graph: list, visited: list, colors: list, node: int, color: int): visited[node] = ..
문제https://www.acmicpc.net/problem/2667 해설DFS와 BFS 모두 사용하여 풀이가 가능한 문제라고 한다. 두 방법 모두 이용하여 풀어보았다. 아직 실력이 초보에 가까워 직관적으로 구현하려고 노력하였다. 이 문제는 DFS가 더 적절한 방법이라고 생각한다. 이 문제에선 DFS의 탐색 속도가 조금 더 빠르기 때문이다. BFS는 주변의 요소만 판단하며 거의 마지막 그리드까지 하나씩 확인해나가야 한다. 반면, DFS는 하나의 hit를 찾았을 때 한 번에 끝까지 모든 인접 경로를 탐색하는 방식이므로 visited 검사를 통해 BFS보다 좀 더 빠르게 조건문에서 필터가 가능하다. 다만 DFS를 사용하였을 땐 Stack Overflow의 위험이 내재되어 있다는 점은 인지하여야 한다. Pyt..
문제https://www.acmicpc.net/problem/1697 해설최단 경로를 탐색하는 문제이므로 BFS를 사용하였다. Pythonqueue에서 pop하는 과정은 deque 자료구조를 활용하여 시간초과에 관한 문제를 개선하였다. 이후 set을 이용하여 visited를 저장하였지만, 메모리 초과가 발생하였다. 이 부분을 list를 이용하여 최대 사이즈를 지정하여 메모리 초과를 해결할 수 있었다. from sys import stdinfrom collections import dequeMAX = 100001def bfs(start: int, end: int): visited = [False] * MAX visited[start] = True queue = deque([(start, ..
문제https://www.acmicpc.net/problem/1260 해설알고리즘 문제에서 자주 활용되는 DFS와 BFS 구현에 대한 문제였다. 모든 Vertex(정점)을 방문할 땐 DFS, BFS 모두 사용하여도 무관하지만 경로의 특징에 따라 처리가 되는 문제라면 DFS를 사용하는 것이 유리하다. 반면 최단거리를 구하는 문제는 BFS를 사용하는 것이 유리하다. 깊이 내려가지 않고 가까운 곳에서 탐색할 수 있기 때문이다. 참고로 간선은 Edge라고 표현한다. Pythonfrom sys import stdindef dfs(graph: list, start: int, visited: list): dfs_result.append(str(start)) visited[start] = True fo..
문제https://www.acmicpc.net/problem/2470 해설완전 탐색으로 풀었을 때 시간초과가 발생하였다. 투 포인터라는 개념을 적용시켜 성능을 개선시킬 수 있었다. Python1차 시도(실패) 완전 탐색으로 풀이하여 시간 초과가 발생하였다. from sys import stdindef solution(N: int, lst: list): current_sum = abs(max(lst)) lst = sorted(lst) result = [lst[0], lst[-1]] for l1 in lst: for l2 in lst[::-1]: if l1 != l2: new_sum = abs(l1+l2) if ..
