본문 바로가기
728x90

너비우선탐색4

[PG/Python] 전력망을 둘로 나누기 📌 문제 https://programmers.co.kr/learn/courses/30/lessons/86971 코딩테스트 연습 - 전력망을 둘로 나누기 9 [[1,3],[2,3],[3,4],[4,5],[4,6],[4,7],[7,8],[7,9]] 3 7 [[1,2],[2,7],[3,7],[3,4],[4,5],[6,7]] 1 programmers.co.kr 📌 문제 접근 방법 인접리스트를 활용해서 연결된 전선 정보를 입력해준다. wires를 한 번 더 반복문을 돌리면서 전선들 중 하나를 끊는다. 이 때 끊긴 두 송전탑을 기준으로 전력망이 가진 송전탑의 개수를 bfs를 활용해서 구해준다. 두 전력망의 송전탑 수와 현재의 answer에 저장된 값을 비교하여 더 작은 값으로 answer 값을 갱신해준다. 끊긴 두.. 2021. 11. 14.
[SWEA/Python] 5250. 최소 비용 📌 문제 https://swexpertacademy.com/main/main.do SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 📌 문제 접근 방법 bfs를 활용해서 인접한 지역으로 이동한다. 이동한 지역이 이동 전 지역보다 높을 경우, 차이를 저장해준다. 이동할 지역에 이미 저장된 비용보다 현재의 경로로 이동할 때의 비용이 더 덜든 다면, 비용을 갱신해준다. (이 조건이 있기 때문에 따로 방문체크를 안해줘도 된다! 방문체크를 하면 오히려 최소 거리로만 이동하게 된다.) 📌 코드 from collections import deque import sys sys.stdin = open('input.txt') de.. 2021. 10. 15.
[BOJ/Python] 17471. 게리맨더링 📌 문제 https://www.acmicpc.net/problem/17471 17471번: 게리맨더링 선거구를 [1, 4], [2, 3, 5, 6]으로 나누면 각 선거구의 인구는 9, 8이 된다. 인구 차이는 1이고, 이 값보다 더 작은 값으로 선거구를 나눌 수는 없다. www.acmicpc.net 📌 문제 접근 방법 N개의 구역을 조합을 이용해서 2개의 선거구로 나눈다. 각 선거구를 bfs를 통해 탐색해서 모든 구역에 방문할 수 있는지 체크한다. 여기서, 선거구에 있는 구역만 탐색을 하는 것이 포인트! (w in group → 이걸 처리 안해줘서 실패가 나왔음!) 2개의 선거구 모두 선거구 안의 모든 구역에 방문할 수 있다면, 인구 수의 차이를 구하고 최소값으로 갱신한다. 📌 코드 # 백준 17471 .. 2021. 10. 13.
[Algorithm] DFS, BFS 그래프 탐색 비선형구조인 그래프 구조는 그래프로 표현된 모든 자료를 빠짐없이 검색하는 것이 중요 두 가지 방법 깊이 우선 탐색 (Depth First Search, DFS) 너비 우선 탐색 (Breadth First Search, BFS) DFS (깊이우선탐색) 시작 정점의 한 방향으로 갈 수 있는 경로가 있는 곳까지 깊이 탐색해 가다가 더 이상 갈 곳이 없게 되면, 가장 마지막에 만났던 갈림길 간선이 있는 정점으로 되돌아와서 다른 방향의 정점으로 탐색을 계속 반복하여 결국 모든 정점을 방문하는 순회방법 마지막에 만났던 갈림길의 정점으로 되돌아가서 깊이 우선 탐색을 반복해야 하므로 후입선출 구조의 스택 사용 DFS 알고리즘 시작 정점 v를 결정하여 반문 정점 v에 인접한 정점 중에서 방문하지 않는 정점 .. 2021. 10. 3.
728x90

티스토리툴바