문제 2178 - 미로 탐색 접근 단순한 2차원 BFS 문제이다. 2차원에서 상하좌우 한칸씩 이동하며 목적지까지 몇 번만에 도달했는지 확인하면 된다. 코드 파이썬 코드 from collections import deque def bfs(): q = deque() q.append((0,0)) visit...

문제 2644 - 촌수계산 접근 문제를 읽었을 때 처음 든 생각은 트리구조였다. 하지만 트리구조로 이 문제를 해결하고자 하면, 굉장히 문제가 까다로워진다. 단순히 a노드에서 BFS를 이용하여 b 노드를 방문하는데 걸린 거리를 구하면 문제는 간단하게 해결된다. 코드 파이썬 코드 from collections import ...

문제 11724 - 연결 요소의 개수 접근 파이썬에서 input을 사용해서 입력을 받으면, 입력이 많을 때 시간초과가 뜬다…. sys를 애용하자. 코드 파이썬 코드 from collections import deque import sys n, m = map(int, sys.stdin.readline().split()) ...

문제 1260 - DFS와 BFS 접근 DFS, BFS를 구현하기만 하면 되므로 설명은 따로 하지 않겠다. 코드 파이썬 코드 from collections import deque n, m, v = map(int, input().split(' ')) adj = [[0]*(n+1) for _ in range(n+1)] vis...

문제 10265 - MT 접근 정말 어려운 문제였다. 앞에서 텀 프로젝트 문제를 푼 것이 크게 도움이 되었고, 해당 내용을 많이 사용하였다. 크게 두 단계로 구성된다. 첫 번째는 사이클을 검사하는 단계이다. 이 단계에서는 텀 프로젝트의 접근법을 기반으로 하여 조금만 추가하였다. 사이클에서 제외된 인원의 수를 구하는 것에 추가적으로...

문제 9466 - 텀 프로젝트 접근 알고리즘을 생각하기까지가 굉장히 어려웠다. 단순히 사이클을 검사하는 것을 넘어서, 사이클을 구성하는 노드들을 제외한 노드를 어떻게 찾을지 많이 고민했다. 특정 노드에 대해서 dfs를 수행하면서, 방문하는 노드들을 배열에 모두 담아두고 있는다. (반드시 순서대로!) dfs를 수행하는 도중에 이미 방문...

문제 10552 - DOM 접근 이 문제의 핵심은 크게 두 가지이다. 첫 번째는 사이클이 생기는지 여부를 파악하는 것이다. 채널을 계속돌릴 때 사이클이 발생했다면, 즉시 중단하고 -1을 출력해야 한다. 두 번째는 현재 채널을 싫어하는 사람이 없는지 체크하는 부분이다. 이는 채널이 돌아갈 때마다 체크를 해주어야 한다. 입력 범위가 ...

문제 2468 - 안전 영역 접근 강수량을 x라고 할 때, board에 x 이하인 칸들은 막혀있다고 생각하면 간단해진다. 그러면 열린 공간들의 개수를 세는 문제인데, 모든 강수량에 대해서 이를 반복해주면 된다. 나는 입력을 받을 때, 최대 높이를 구해두고, 강수량을 1부터 최대 높이까지 반복하며 영역의 개수를 구해주었다. 코드 ...

문제 11403 - 경로 찾기 접근 특정 노드 a, b 가 있을 때, a와 b가 연결되어 있는지 확인하는 문제이다. 이 때 a, b가 바로 연결되어 있다면 문제가 없겠지만, (a, k), (k, b)로 중간 노드를 거치는 경우를 어떻게 해결할지가 관건이다. 나는 모든 노드 k에 대해 반복문을 돌며 k를 중간 지점으로 가지는 노드들에 대...

문제 가장 먼 노드 접근 1번 노드에서부터 각 노드까지의 거리를 구하면 된다. 따로 가중치가 없으므로 단순하게 BFS를 돌며 몇 번만에 도달했는지만 확인하면 된다. 코드 파이썬 코드 def solution(n, edge): answer = 0 dis = [-1] * (n+1) e = {} for ...