BFS

백준 7569 토마토 (BFS, 3차원)

이번 문제는 저번 7576문제를 3차원으로 바꾼 문제이다. https://guccin.tistory.com/92 백준 7576 토마토 (BFS, 행렬 그래프, python) 이번 문제는 원리도 파악하고 간단히 풀수 있다고 생각하고 코딩을 진행했다. 모든 예를 통과하고 반례도 통과하며 잘 코딩했다고 생각했으나 시간초과의 벽을 넘지 못하고 고수들의 코드를 보 guccin.tistory.com 조건은 똑같다. 하루마다 양 사이드의 토마토가 익어가는데 추가되는 조건은 위아래 상자도 같이 적용된다는 것이다. 대충 3차원으로 생각해보고 위아래 같이 익게하는 조건을 추가하면 끝이다. from collections import deque m,n,h = map(int, input().split()) #열 행 상자수 q ..

백준 1697 숨바꼭질 (BFS)

이거 어렵지는 않았다. 그냥 BFS로 원하는 목표치가 나올때까지 갯수를 확인하면서 루프를 돌리면 된다. 내가 헤맨 부분은 이동할때 2배로 이동하는 부분이 존재하기 때문에 start 점과 end점을 (start = 0 and visited[t-1]==0: tmp.append(t-1) visited[t-1] = 1 if t+1

백준 7576 토마토 (BFS, 행렬 그래프, python)

이번 문제는 원리도 파악하고 간단히 풀수 있다고 생각하고 코딩을 진행했다. 모든 예를 통과하고 반례도 통과하며 잘 코딩했다고 생각했으나 시간초과의 벽을 넘지 못하고 고수들의 코드를 보게 되었다. 원리는 어렵지 않다. 1. 토마토가 존재하는 곳을 찾아서 큐에 넣어준다. 2. 큐에서 하나씩 꺼내며 너비탐색을 진행한다. 3. 탐색이 끝나면 익지 않은 토마토가 존재하는지 확인한다. 4. 전부 익었다면 걸린 날짜를 출력, 익지 않은게 있다면 -1을 출력한다. 이를 토대로 코딩을 진행했다. 그러나 아래의 코드는 시간초과로 쓸수가 없었다. from collections import deque m,n = map(int, input().split()) L = [] for _ in range(n): tmp = list(m..

백준 2178 미로 탐색 (BFS, 최단 경로 탐색, 행렬그래프)

이번 문제는 BFS를 어떻게 최단경로로 활용할건지 이해해야한다. 처음에는 나도 BFS로 어떻게 최단경로를 구한다는 소리인지 알 수 없었다. 나도 완벽하게 이해하고 풀지 않았기 때문에 생각의 흐름을 나열해 볼까 한다. 우선 행렬그래프를 BFS의 트리 형태로 나열한다고 가정한다면 다음과 같은 그래프를 만들 수 있다. 그렇다면 우리는 (4,4)가 되기 위해서 7층까지 내려가야한다는 것을 단숨에 확인 가능하다. 그렇다면 BFS로 탐색을 하면서 언제가 몇층인지를 알아야한다. 따라서 층을 함께 표기해본다. 그러면 (1,1)이 1층인것을 알기 때문에 층에 큐에 넣은 인접 행렬에 대해서 2층이라는 것을 표기하여 큐에 삽입할 수 있다. 이러한 방식으로 (4,4)까지 진행하면 간단히 (4,4)가 7층에 있는 것을 알 수 ..

백준 2667 단지번호붙이기 (DFS, 그래프 탐색)

이번 문제는 생각보다 쉽게 풀렸다. DFS의 기본 코딩 구조를 알면 바로 대입이 가능한 문제였다. 문제는 1이 집들이고 붙어 있는 집끼리 단지를 조성한다. 그리고 단지의 개수를 확인하고 단지별 개수를 오름차순으로 출력하는 문제이다. 이 문제를 풀기 위해서는 뇌피셜로 필요하다고 생각되는 요소를 정리해 보았다. 1. DFS를 스택을 활용하여 코딩을 구현할 수 있는지 2. DFS로 행렬들의 인접을 어떻게 파악할건지 3. 다음 단지는 어떻게 찾을건지 우선 DFS를 스택을 활용하여 코딩하는건 넘어간다. 그럼 2번 DFS로 행렬들의 인접을 어떻게 파악할건지 생각해본다. 현재 (0,1)에서 가장 먼저 집이 발견된다. 문제는 동서남북 모두 확인하여 인접한 행렬을 확인해야 하는데 위에는 접근할 수가 없다. 따라서 에 패..

백준 1260 풀이 (DFS, BFS, 그래프 탐색)

이번 문제는 그래프 탐색 문제이다. 그래프가 주어지면 이것을 DFS,BFS방식으로 탐색하여 순서를 나타내면 된다. DFS, BFS의 개념은 알고 있었지만 막상 코딩으로 짜려니 상당히 헤매었다. DFS를 설명하자면 깊이 우선 탐색방법으로 깊게 들어가는 가며 탐색하는 방법이다 원리는 구글에 자세히 나온다. 처음 도움을 받은 곳은 www.youtube.com/watch?v=_hxFgg7TLZQ 로 영상을 보고 대강 이해를 하고 코드를 짜기 시작했다. 간단히 설명하자면 DFS => stack으로 탐색 가능. 연결되는 노드를 차례로 스택에 저장 BFS => queue로 탐색 가능. 연결되는 노드를 차례로 큐에 저장 자세한 로직은 유튜브를 참고하면 될것이다. 물론 유튜브 과정 그대로 코딩을 하려니 코드가 길고 더러..