JINWOOJUNG

접근법 단순히 현재 노드의 부모를 찾는거기 때문에, dfs(),bfs()없이 단순하게 해결할 수 있을 것 같아서 아래와 같이 접근했다. import sys N = int(input()) visited = [0] * (N+1) visited[1] = 1 for _ in range(N-1): x, y = map(int,sys.stdin.readline().split(" ")) if visited[x] != 0: visited[y] = x else: visited[x] = y for i in range(2,N+1): print(visited[i]) 입력받는 두 수 중 하나는 무조건 이전에 언급된 노드여야 루트가 1인 트리를 형성할 수 있다. 따라서 입력받음과 동시에 두 수 중 방문되었던 노드가 있다면 다른 노..

접근법 기존의 dfs에서 대각선을 탐색하는 경우의 수를 추가해 줘야 하며, "0 0"을 입력받기 전까지 반복해야 함으로 반복할 때 마다 전체 그래프와 cnt를 초기화 해 줘야 한다. 따라서 dfs()의 parameter에 전체 그래프도 추가되어야 한다. 정답 import sys sys.setrecursionlimit(10**6) di = [0,0,-1,1,1,1,-1,-1] dj = [1,-1,0,0,1,-1,1,-1] def dfs(i, j, Map): Map[i][j] = 0 for k in range(8): I = i+di[k] J = j+dj[k] if 0

접근법 dfs를 활용하여 접근하였고, 방문하지 않은 노드에 대하여 dfs를 적용한다면, 연결된 노드들을 방문하고 만약 연결이 안된 다른 그룹이 있다면, 연결 요소의 개수를 증가시키고 다시 dfs를 적용시키면 된다. 정답 import sys sys.setrecursionlimit(10**9) M, N= map(int, sys.stdin.readline().split()) visited = [False]*(M+1) graph = [[]for _ in range(M+1)] for _ in range(N): x, y = map(int, sys.stdin.readline().split()) graph[x].append(y) graph[y].append(x) def dfs(start): visited[start] ..

접근법 처음에는 N으로 입력값은 높이에 대한 안전 영역 을 계산하였지만 문제를 잘못 접근 한 것이었다. 높이가 최소인 1부터, 각 위치의 높이가 쵀대인 값 까지 모두 고려하였을 때, 안전 영역이 최대가 되는 경우를 생각해야 한다. 즉 높이가 1부터 최대로 H까지 존재한다면,1~H 이하인 지점을 모두 잠기게 만드는 상황을 고려해야 한다. 만약 H이하인 경우 모두 잠기기 때문에 1~H-1까지 고려해서 최대인 안전 영역 을 계산하면 된다. dfs()로 접근하여 해결하였으며, 여러번 계산해야 하므로 할때마다 방문한 위치를 표시하기 위한 변수 visited와 안전 영역 의 개수인 cnt를 초기화 한다. 정답 import sys sys.setrecursionlimit(10**9) N = int(input()) la..

접근법 어려웠다.. 단순히 dfs 측면으로 접근하고자 했는데 " 1->3->2->3" 과 같이 일치하지 않는 집합을 거름과 동시에 중간에 일치하는 집합을 찾아내는 아이디어를 도출하는게 매우 힘들었다... 정답 import sys sys.setrecursionlimit(10**6) N = int(input()) graph = [[] for _ in range(N+1)] for i in range(1,N+1): graph[int(input())].append(i) visited = [0]*(N+1) result = set() def dfs(i, arr): for j in graph[i]: if visited[j]: while arr: tmp = arr.pop() result.add(tmp) if j == t..

접근법 다른 두 수의 합으로 특정 수를 나타내는지를 확인하기 위해서는 특정 수 보다 작은 두 수를 선택해야 하기에 정렬이 필요하다. 또한, 이중 for문으로 직접 접근하기에는 두 수를 찾기 위한 while문이 추가적으로 필요하여 $O(n^3)$ 시간복잡도가 발생한다. 따라서 $nlogn$의 알고리즘이 필요하기에 quick sort에서 활용한 방식처럼 pointer를 이용하여 접근하였으며, 0과 자기자신이 더해져 다른 위치의 자기자신을 나타내는 예외사항을 처리하도록 노력하였다. 정답 import sys N = int(input()) arr = list(map(int,sys.stdin.readline().split(" "))) arr.sort() cnt = 0 for i in range(N): tmp = a..

접근법 최소 비교 횟수를 구하기 위해서는 입력받은 묶음의 크기를 정렬한 후 작은 2개의 묶음의 크기부터 더해나가서 계산할 수 있다. 따라서 양쪽으로 입출력이 가능한 deque 자료구조를 사용하여 구현하였다. from collections import deque N = int(input()) tmp = [] for i in range(N): tmp.append(int(input())) tmp.sort() queue = deque() for i in range(N): queue.append(tmp[i]) result = 0 for _ in range(1,N): a = queue.popleft() b = queue.popleft() result += a+b queue.appendleft(a+b) print(r..

접근법 기본적인 아이디어는 DFS를 생각했고, 여기서 특이점은 R,G를 동일하게 인식해야 한다는 점이다. 따라서 DFS를 적용할 때 B가 아닌 위치를 다른 배열에 체크해 둔 후, 해당 배열에 한번 더 DFS를 적용하여 적록색약인 경우에 구역의 수를 계산 하였다. 정답 import sys sys.setrecursionlimit(10**9) dx = [0,0,-1,1] dy = [-1,1,0,0] N = int(input()) def dfs(x,y,color): image[y][x] = 0 if color != "B": check[y][x] = 1 for i in range(4): X = x + dx[i] Y = y + dy[i] if(0