토피넛라떼조아

지난 포스팅을 통해 DFS를 알아보았으니 형제 탐색법인 BFS를 알아보겠다.BFS 또한 DFS처럼 트리나 그래프를 순회하는 기본 방법 중 하나이다. BFS (Breadth First Search)? BFS는 너비 우선 탐색이다. 시작 노드부터 가까운 노드들을 모두 살펴본 뒤 그 다음 노드들을 탐색한다. 단순하게 생각해서 파원에서 파장이 퍼져나가는 모양을 생각하면 얼추 비슷하다. 특징과 장단점- 연결된 모든 노드를 탐색할 수 있다.- 방문 노드를 기억하고 재방문하지 않는다.- DFS가 스택을 활용하는 것과 다르게 보통 큐를 활용한다.- 최단경로 탐색에 적절하다. 해를 찾고나면 다음 해는 찾을 필요가 없기 때문이다.- 논리 구조가 간단하다.- 해가 깊은 곳에 있으면 탐색에 오랜 시간이 걸릴 수 있다.  BF..

문제 출처 : https://www.acmicpc.net/problem/1325

문제 출처 : https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5V61LqAf8DFAWu&categoryId=AV5V61LqAf8DFAWu&categoryType=CODE&problemTitle=%ED%99%88+%EB%B0%A9%EB%B2%94&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=1 SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 🔥 작성코드 # bfs def sol(si, sj, k): global result q..

문제 출처 : https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5PpLlKAQ4DFAUq&categoryId=AV5PpLlKAQ4DFAUq&categoryType=CODE&problemTitle=%ED%83%88%EC%A3%BC%EB%B2%94&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=1 SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 🔥 작성코드 # bfs def sol(R, C): global result q = [[R..

https://swexpertacademy.com/main/learn/course/lectureProblemViewer.do SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 🔥 작성 코드 def bfs(si, sj, N): # 초기 데이터 설정 q = [] v = [[-1]*N for _ in range(N)] q.append([si, sj]) v[si][sj] = 0 while q: si, sj = q.pop(0) # 4방향 탐색 for di, dj in ((1, 0), (-1, 0), (0, -1), (0, 1)): ni, nj = si+di, sj+dj # 갈 수 있다면 q에 삽입, 방문 배열에 이전 값 ..