토마토 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 알고리즘 일반적인 그래프 탐색과 달리, 입력된 초기 그래프에서 1이 있는 곳을 동시에 인접 지역을 탐색해야 한다. 즉, 시작점이 여러 개다. 시작점을 미리 queue에 넣어서 방문할 수 있도록 한다. 1이 있는 지점을 방문하면서 인접 장소를 탐색한다. 이때 익지 않은 토마토가 있다면 방문하고, 몇 번째 날짜인지 기록한다. 이 부분을 print로 찍어보면 다음과 같이 나온다. 일단 queue에 익은 토마토(1)의 위치를 모두 append 해..

BFS와 최단 경로 BFS는 최단거리와 관련있다. 왤까? BFS 알고리즘과 구현에 대해 이해하면, 이에 대한 해답을 얻을 수 있다. BFS 알고리즘을 이해하기 위해서는 먼저 bfs 알고리즘이 node를 방문하는 순서를 살펴봐야 한다. bfs는 위 그림과 같이 인접한 노드를 먼저 방문한다. 그리고 방문한 순서대로 노드들을 Q에 넣고 시작점에서 인접한 Node를 모두 방문하면, Q 맨앞의 노드를 popleft한다. 이후 popleft된 노드들의 인접한 노드를 탐색하여 이 노드들도 똑같이 Q에 저장한다. 결론적으로 queue는 선입선출 방식으로 동작되기 때문에 방문 노드들이 순서대로 queue에 저장된다. 흠.. 이렇게만 봐서는 왜 최단경로인지 모르겠다;; 예시를 보자. 시작점 A에서 F까지의 최단경로를 알아..

https://www.acmicpc.net/problem/3184 3184번: 양 첫 줄에는 두 정수 R과 C가 주어지며(3 ≤ R, C ≤ 250), 각 수는 마당의 행과 열의 수를 의미한다. 다음 R개의 줄은 C개의 글자를 가진다. 이들은 마당의 구조(울타리, 양, 늑대의 위치)를 의미한다. www.acmicpc.net 알고리즘 그래프 탐색 문제인 건 알겠는데, 같은 영역을 어떻게 판단하지?가 고민이었다. 적록색약 문제에서는 bfs 함수에서 같은 색을 만나면 계속해서 q에 그 지점을 삽입하면서 탐색을 하게 만들었는데, 얘도 마찬가지다..! 그래서 ⭐️⭐️⭐️⭐️⭐️ bfs 함수의 q가 모두 끝나면 ⭐️한 영역⭐️에 대한 큐가 끝나는 것임..⭐️⭐️⭐️⭐️⭐️ 그니까 while q 이 부분이 주변을 탐..

dfs : 최대한 깊게 방문하지 않은 노드들에 쭉 방문하다가, 더이상 진행할 수 있는 인접정점이 없으면 되돌아감 - 재귀 bfs : 한 노드에서 인접노드까지 방문한 적이 없는 모든 노드를 queue에 삽입. que는 FIFO 방식이라서 순차적인 구현 가능 popleft로 앞에거 빼주면 됨 ㅇㅇ dfs 구현 from collections import deque r,c = map(int, input().split()) pasture = [list(input()) for _ in range(r)] visit = [[0]*c for _ in range(r)] d = [(0,1),(0,-1),(1,0),(-1,0)] cnt = 0 def dfs(x, y) : visit[x][y] = 1 for dx, dy in ..