DFS

[python3] 1167 풀이 (트리의 지름, 트리, DFS)

문제가 어려워서 힌트를 봤고 이해하고 나니 쉽게 풀 수 있었다. 트리가 주어진다. 이때 트리의 지름을 구하는 문제이다. 트리의 지름을 어떻게 구해야하는지 이해하지 못하면 풀수가 없다. 트리가 주어졌을대 트리의 지름을 구하기 위해서는 가장 끝점을 알아내야한다. 처음에는 각 노드마다 다익스트라를 할지 플로이드를 할지 고민했다. 그런데 주어지는 노드가 100,000개이기 때문에 구할 수가 없다. 따라서 다른 방법을 사용해야한다. 그래서 이리저리 지지고 볶으니 한줄로 세우는 방법이면 되지 않을까 싶었다. 그래서 한줄로 세워보았다. 그런데 이렇게 세운다고 달라지지가 않았다. 더이상 고민하는게 무의미하여 찾아보니 아무 노드나 잡고 가장 먼것을 찾아본다. 그럼 지름의 끝 노드를 찾을 수 있었다. 만약 3번 노드에서 ..

[python] 조합을 DFS로 구하기

항상 combinations로만 조합을 구했는데 이제는 한번 정리를 해야할것 같아서 오랜만에 글을 쓴다. 이문제는 백준 15650번으로 조합을 구하면 되는 문제이다. 사실 라이브러리를 사용한다면 상당히 쉬운 문제이다. from itertools import combinations N, M = map(int, input().split()) for com in list(combinations([i for i in range(1, N+1)], M)): print(" ".join(map(str, com))) 그러나 이렇게 푸는게 습관이 되어 나중에 백트래킹 문제가 어렵게 느껴졌고 기초적인 문제를 코테에서 틀리는 상황이 발생했다. 따라서 이걸 DFS로 풀어보자. 4에서 3개를 뽑는 경우는 [1,2,3],[1,2,..

[python3] 백준 1520 풀이 ( 내리막길, DP, DFS, 그래프 )

이번 문제 풀이 사실 봐버렸다. 거의 풀었다고 생각했는데 내가 생각한 방법으로는 도저히 풀리지가 않아서 그냥 풀이를 봤다. 바로 문제를 보자 문제를 읽어보면 낮은 방향으로만 진행한다고 한다. -> 사이클이 존재하지 않는 그래프이다. 가장 빠른게 도착하는게 아닌 도착하는 경우의 수를 구한다. -> BFS가 아닌 DFS를 여러 번 써야한다. 문제를 통해 2가지를 확인할 수 있다. 그런데 DFS만을 쓰는 경우에는 너무 많은 케이스가 존재한다. 실제로 DFS만으로 제출한다면 시간초과가 뜬다. 따라서 DFS만이 아닌 DP를 함께 활용해 주어야한다. 그럼 DP를 어떻게 활용해야 할지 고민을 해본다. DFS만 써서 시간초과가 나는 것은 빙빙 돌아 목적지에 도착하는 경우까지 기다려야 하기 때문이다. 그렇다면 빙빙 돌아..

[python3] 백준 1967 풀이 (트리의 지름, DFS)

이 문제는 그림을 보면 이해가 빨라진다. 우리는 각 노드를 쫙 잡아당겼을때 길이가 가장 길어지도록 하는 길이를 찾아야 한다. 만약 오른쪽 그림이 가장 길게 잡아당겨진 형태라고 가정한다. 그럼 오른쪽에 회색 노드들 중에서 아무거나 잡고 DFS를 통해 가장 먼 노드를 찾으면 그건 무조건 파란색 노드가 된다. 신기하게도 어떤 노드를 택하던 가장 먼 노드를 찾으면 그건 파란색 노드가 되는것이다. 진짜 신기하다. 그렇게 파란색 노드를 하나 찾고, 이번에 찾은 파란색 노드로부터 가장 먼 길이를 찾으면 우리가 찾고자하는 트리의 길이가 된다...... 그럼 DFS를 단 2번만 하면 해결되는 문제이다. 그럼 DFS할 때 각 길이만 저장하면서 확인하면 되는 것이다. 1. DFS(1)로 파란색 노드하나 찾기 2. DFS(B..

[python3] 백준 1937 풀이 (욕심쟁이 판다, DFS, DP)

어떤 문제이던 DP가 들어가면 난이가 확 올라가는것 같다. 이 문제는 처음에는 DFS로만 풀었다. 각 좌표별로 DFS를 실행했고 DFS에 시간복잡도에 N*N만큼 곱해져서 상당히 시간복잡도가 컸다. 그래서 시간초과가 났고 새로운 풀이를 찾아야 했다. 우선 고수들의 예시를 보자 위와 같이 대나무가 있다고 가정한다. 우리는 (0,0)부터 탐색을 시작한다. 그렇다면 자신보다 큰 값으로 최대한 이동할때의 DFS를 생각해본다. 그렇다면 DP배열은 아래와 같이 설정된다. 그러면 결국 DFS한번 만으로 각 좌표에서의 최대 일 수를 구할 수 있다. 그렇다면 DP가 계산되지 않은 (1,0)을 살펴본다. 그러면 이미 DP(0,0)은 최댓값을 가지고 있으므로 2의 값을 가져와서 1을 추가한다면 DFS없이 최대 일 수를 구할 ..

[py3] 백준 2573 풀이 (빙산, DFS, 그래프)

이 문제는 일반적인 그래프에서 집합 개수 찾는 것과 시간마다 달라지는 그래프를 적용하여 푸는 문제이다. 여기서 중요하다고 느낀점은 빙하가 물과 닿는 개수대로 빙하가 녹게 되는데 녹일때 조심해야한다. 예를 들어 0 0 0 0 3 5 0 0 0 이라고 한다면 내년에는 0 0 0 0 0 3 0 0 0 이 되어야한다. 그러나 코드를 잘못짜면 0 0 0 0 0 2 0 0 0 이 될수 있다. 그래서 나는 filter 배열을 만들고 빙하별로 인접한 방향의 수를 구하고 제거하는 방식으로 코드를 구현했다. n,m = map(int , input().split()) M = [] big = 0 for _ in range(n): tmp = list(map(int, input().split())) M.append(tmp) fr..

백준 10026 파이썬 풀이 (적록색약, DFS)

이번 문제는 간단하다. 그냥 같은 영역이 얼마나 되는지 찾아내는 것이다. 1. 일반인을 위한 Map, 적록색약인 사람을 위한 Map('G'와 'R'를 동일하게 보는 사람) 2. DFS를 유연하게 만들어서 시간을 줄인다. n = int(input()) NMap = [] WMap = [] for i in range(n): tmp = list(input()) NMap.append(list(tmp)) for j in range(n): if tmp[j] == "G": tmp[j] = "R" WMap.append(tmp) def DFS(x,y, Map): s = [(x,y,Map[x][y])] Map[x][y] = 0 dx = [0,0,1,-1] #동서남북 dy = [1,-1,0,0] while s: x,y,z =..

백준 2583 파이썬 풀이 (영역 구하기, DFS)

이번 문제는 주어진 좌표만큼 색칠된 경우 색칠되지 않은 영역의 넓이와 개수를 구하면 된다. 1. 좌표를 배열위치로 바꾸기 2. DFS로 탐색하면서 넓이 구하기 이 두가지만 하면된다. 좌표는 그림을 그려서 구해보면 쉽게 확인가능하다. start = [(m-1-b),(0+a)] end = [(m-d),(c-1)] 로 바꾸면 된다. 그럼 DFS로 탐색하는 코드만 추가해주면 끝이다. m,n,k = map(int, input().split()) Map = [[0 for i in range(n)] for i in range(m)] for _ in range(k): a,b,c,d = map(int, input().split()) start = [(m-1-b),(0+a)] end = [(m-d),(c-1)] for i..