반응형 알고리즘/DFS_BFS4 [백준] 18352번: 특정 거리의 도시 찾기(Python) | LIM 1. 문제 2. 첫 번째 시도( 메모리 초과 발생 ) 3. 두 번째 시도( 시간 초과 발생 ) 3. 세 번째 시도( 틀린 원인과 정답 ) 📚 문제 어떤 나라에는 1번부터 N번까지의 도시와 M개의 단방향 도로가 존재한다. 모든 도로의 거리는 1이다. 이 때 특정한 도시 X로부터 출발하여 도달할 수 있는 모든 도시 중에서, 최단 거리가 정확히 K인 모든 도시들의 번호를 출력하는 프로그램을 작성하시오. 또한 출발 도시 X에서 출발 도시 X로 가는 최단 거리는 항상 0이라고 가정한다. 예를 들어 N=4, K=2, X=1일 때 다음과 같이 그래프가 구성되어 있다고 가정하자. 이 때 1번 도시에서 출발하여 도달할 수 있는 도시 중에서, 최단 거리가 2인 도시는 4번 도시 뿐이다. 2번과 3번 도시의 경우, 최단 거.. 2022. 12. 18. [백준] 14888번: 연산자 끼워넣기 Python (DFS, BFS) | LIM 이 문제의 경우는 순서대로 연산자에 상관없이 계산해야하기 때문에 연산자를 하나씩 뽑아서 즉, popleft를 사용하여 구현해야 한다고 생각했다. 즉 BFS를 사용하여 문제를 해결하였다. 1. 숫자는 순서의 바뀌지 않고 연산자의 순서만 바뀌기 때문에 연산자의 조합이 어떻게 올 지 부터 먼저 구해야 한다. (조합은 permutation을 이용하여 구했다. 다만, permutation의 경우 ['+','+','+','+']의 경우 모두 다르게 인식하여 경우의 수를 많이 만들기 때문에 set을 사용하여 조합을 unique한 상태로 변경해야 한다.) 2. 연산자의 특성 중 나눗셈 부분이 기존 나눗셈의 개념과는 다르기 때문에 나같은 경우 함수로 사칙연산을 구현해주었다. (생각보다 시간이 오래 걸리지 않았다..) 3.. 2021. 9. 12. [백준] 18405번: 경쟁적 전염 Python (DFS, BFS) | LIM 이 문제는 BFS를 이용하여 풀었다. 생각보다 이 문제는 간단하게 풀 수 있었다. 먼저, 바이러스가 존재하는 위치와 그 위치에 바이러스 값을 저장했다. 또한, 바이러스 숫자가 작을수록 우선수위를 갖기 때문에 바이러스 숫자가 작은 순서대로 sorting 해주었다. popleft()를 통해 앞에 있는 것(바이러스 숫자가 작은것)부터 뽑아내며 상하좌우로 퍼지게 하였다. 퍼지게 한 후 바이러스가 전염된 부분의 바이러스 값과 인덱스를 기존 virusIndex에다가 뒤로 저장하였다. 맨 처음에 순서대로 sorting 해주었기 때문에 추후에 저장되는 바이러스 값은 자동으로 정렬이 되어 있다. 기존에 있던 바이러스가 모두 popleft()를 통해 사라지고 그 바이러스를 통해 전염된 바이러스와 인덱스만 남게 되면 시간을.. 2021. 8. 31. [백준] 14502번: 연구소 Python (DFS, BFS) | LIM DFS와 BFS에 관련하여 설명은 너무 많기에 내가 기억하고 싶은 것만 정리하고자 한다. DFS - Depth-First Search(깊이 우선 탐색) 즉, 깊은 부분부터 탐색하겠다는 이야기이다. 깊은 부분부터 탐색한다는 말이 사실 잘 이해가 되지 않기에 그냥 DFS는 스택을 사용한다로 외웠다. DFS는 스택을 이용하는 알고리즘이기 때문에 실제 구현은 재귀함수를 이용했을 때 매우 간결하게 구현할 수 있다. 스택은 박스 쌓기에 비유할 수 있다. 박스를 쌓다가 아래에 있는 박스를 치우기 위해서는 위에 박스부터 먼저 치워야 한다. 이러한 구조를 선입후출, 후입선출 구조라고 한다. 그냥 먼저 들어온게 나중에 나간다고 생각하면 쉽다. 왜냐하면 쌓기 때문이다. DFS가 동작하는 과정은 다음과 같다. 1. 탐색 시작.. 2021. 8. 31. 이전 1 다음 반응형
