알파벳오랜만의 백준 포스팅!!코테에서 부족함을 절실히x99 느끼고 다시 알고리즘을 본격적으로 시작했다..🥲🤗 문제 바로 가기  알고리즘 말이 보드를 탐색하는 조건은 다음과 같다.① (1,1)부터 탐색한다.② 지금까지 지나온 모든 칸에 적혀있는 알파벳과 달라야 이동할 수 있다. 이 조건 아래에서 가능한 경로 중 최대한 큰 수를 구하는 것이 목표다.따라서, DFS를 통해 탐색하는 방법을 선택했다.  def dfs(y,x,cnt): visited[y][x] = True alphabet[ord(graph[y][x])-65] = True # print('시작점: ', graph[y][x]) # 현재 위치에서 네 방향의 위치 확인 for dy, dx in dr: ny, nx..

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 ..