탐색
백준 2667: 단지번호붙이기 해설- python
✏️ 문제 https://www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net ✏️ 풀이 BFS가 편해서 BFS를 이용해서 풀이하였다. 백준 2178: 미로찾기와 백준 11724: 연결요소의 개수 가 혼재된 느낌의 문제였다. 두개 문제의 아이디어를 섞으면 풀린다. 그래프 탐색 시작점을 모르니까 그래프 전체를 반복문으로 돌면서 bfs를 시작한다. 이때 bfs를 하면서 탐색이 된 위치는 0으로 바꾸어 다시 탐색하는 일이 없도록 해주면 된다. 이렇게해서 bfs()를 몇번..
백준 2606: 바이러스 해설- python
✏️ 문제 https://www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어 www.acmicpc.net ✏️ 풀이 아이디어는 간단하다. BFS를 이용해 1부터 아래로 쭉 탐색해 리스트에 저장하고 리스트의 길이를 출력했다. 입력데이터의 표현방식은 인접행렬을 이용했다. from collections import deque n=int(input()) m=int(input()) # 인접영행렬 matrix = [[0]*(n+1) for i in range(n+1)] # 입력받는 값에 대해 영형렬에 1삽..
백준 1260: DFS와 BFS 해설 (파이썬, node.js)
✏️ 문제 https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net ✏️ DFS와 BFS 개념 DFS와 BFS 개념부터가 가물가물해서 처음부터 정리하려고한다. DFS(Depth-First-Search, 깊이우선탐색) 그림이 좋길래 가져와봤다. 탐색순서: 1->2->4->8->5->3->6->7 (1) 탐색시작노드를 스택에 삽입하고 방문처리를 한다. (2) 스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있..