그래프탐색 (3) 썸네일형 리스트형 [백준] 바이러스 2606 파이썬 https://www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어 www.acmicpc.net 문제 설명 해당 문제는 단순히 그래프탐색을 해서 방문 가능한 노드가 총 몇개인지 확인하는 문제였다. 나는 이전에 DFS, BFS문제를 n x n으로 취급해서 문제를 풀었으나 그렇게 하면 시간복잡도가 상당히 높아지기에 인접리스트꼴로 문제를 풀었다. from collections import deque def bfs(graph, visit): q = deque() q.append(1) visit[1] = .. [백준] 5639 이진 검색 트리 (JAVA) https://www.acmicpc.net/problem/5639 5639번: 이진 검색 트리 트리를 전위 순회한 결과가 주어진다. 노드에 들어있는 키의 값은 106보다 작은 양의 정수이다. 모든 값은 한 줄에 하나씩 주어지며, 노드의 수는 10,000개 이하이다. 같은 키를 가지는 노드는 없다 www.acmicpc.net 풀이 이 문제는 기본적인 BST이다. 필자는 이전에 학교에서 BST를 배웠는데 그때는 c언어로 해서 그렇게 크게 어렵지 않았다. 그러나 지금은 자바로 해서 c언어로 할때보다 새로운 느낌이었다. 아무튼 문제의 풀이를 하자면 자바에서는 포인터의 개념이 없기 떄문에 다음과 같이한다. 1. node라는 클래스를 만들고 attribute로는 값을 저장하는 num과 왼쪽과 오른쪽 자식을 가리키게.. [백준] 4963 섬의 개수 (JAVA) https://www.acmicpc.net/problem/4963 4963번: 섬의 개수 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다. 둘째 줄부터 h개 줄에는 지도 www.acmicpc.net 풀이 위의 문제는 예전에 풀었던 백준1012번과 동일하다 문제에서 갈수있는 섬의 개수를 구하라고 했는데 이는 DFS혹은 BFS로 탐색할수있는 섬들의 집합이 몇개나 있는지 물어보는 문제이다. 우선 상하좌우 대각선으로 갈수있는 집합을 만들어주고 그다음 BufferdReader로 읽어서 visit와 map을 초기화 시켜준다. 그 이후 만약 현재 위치가 바다가 아닌 섬이고 미방문한 지역중 섬인 지역.. 이전 1 다음
