그래프4 [백준] 2667. 단지번호붙이기 - Python [Silver I] https://www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net 풀이 2차원 배열을 통해 그래프를 생성하고, 1이 있는 곳 마다 BFS를 돌려 1번 컴퓨터와 연결된 컴퓨터의 개수를 센다. (단지별로 BFS를 돌며, 이미 방문한 곳은 visited 셋을 통해 체크하여 이미 방문한 단지를 중복방문하지 않게 한다.) from collections import deque import sys # global var n = 0 g = [] dx = [-.. 2023. 9. 18. [백준] 2606. 바이러스 - Python [Silver III] https://www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하인 양의 정수이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍 www.acmicpc.net 풀이 2차원 배열을 통해 네트워크(그래프)를 생성하고, BFS를 돌려 1번 컴퓨터와 연결된 컴퓨터의 개수를 센다. from collections import deque computers = [] visited = [] ans = 0 def solve(cur): global ans global visited global computers q = deque() q.append(cur.. 2023. 9. 18. [백준] 1260. DFS와 BFS - Python [Silver II] https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 풀이 2차원 배열을 통해 네트워크(그래프)를 생성하고, BFS와 DFS를 각각 돌려 결과를 출력한다. 정점 번호가 작은 것 먼저 방문해야 하므로, 그래프를 돌면서 각 정점들을 정렬한 후 DFS와 BFS를 실행한다. DFS이후 visited 리스트를 초기화해야 BFS도 동일하게 실행할 수 있기 때문에 DFS 이후 initVar()를 통해 리.. 2023. 9. 18. [백준] 14502. 연구소 - Python [Gold IV] https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 풀이 백트래킹을 통해 미로에서 벽을 놓을 위치 세 곳을 선택한다. -> 나중에는 순열로 해결해도 가능 (1)을 통해 3개의 벽을 세웠으면, 해당 연구실 지도를 deepcopy(깊은 복사를 해야 원본이 변경되지 않음)를 통해 테스트 지도를 복사하고, 상, 하, 좌, 우를 번갈아가며 BFS로 지도를 탐색한다. (처음에는 방문했던 노드를 재방문 하는 것을 피하려고 visited 배열을 사용했지만,.. 2023. 9. 17. 이전 1 다음
