Algorithm (175) 썸네일형 리스트형 [BOJ] 2602. 바이러스 https://www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어 www.acmicpc.net 1. 해결방법 """ 1. 아이디어 - 그래프 배열에서 a vertex에 b vertex를 append 시킨다. - BFS 돌면서 다녀간 vertex는 방문기록 배열로 처리한다. - BFS를 돌면서 감염된 컴퓨터의 수를 구한다. 2. 시간복잡도 - O(n^2) : 100^2 X M 3. 자료구조 - 2차원 배열 : int[][], bool[][] - BFS : Queue """ 2. 정답코드 입력 예제.. [BOJ] 1260. DFS와 BFS https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 1. 해결방법 """ 1. 아이디어 - 공통 : 방문기록(chk)가 중복되지 않도록 방문기록 2차원 배열을 2개 만듬. - 공통 : 양방향 이동이 가능하기 떄문에 a vertex 위치에 b를 append 하는 배열과 b, a 반대도 똑같이 배열에 넣는다. - BFS : 큐에 a와 b가 append괸 그래프 배열을 순서대로 삽입하고 방문한다. 방문기록도 Fals.. [BOJ] 18325. 특정 거리의 도시 찾기 https://www.acmicpc.net/problem/18352 18352번: 특정 거리의 도시 찾기 첫째 줄에 도시의 개수 N, 도로의 개수 M, 거리 정보 K, 출발 도시의 번호 X가 주어진다. (2 ≤ N ≤ 300,000, 1 ≤ M ≤ 1,000,000, 1 ≤ K ≤ 300,000, 1 ≤ X ≤ N) 둘째 줄부터 M개의 줄에 걸쳐서 두 개 www.acmicpc.net 1. 해결 방법 """ 1. 아이디어 - a와 b로 이루어진 1차원 배열 m개, 방문 기록을 판단할 수 있는 1차원 배열 n+1개, 거리 값을 삽입시킨 1차원 배열 n+1개 - 시작지점 x부터 시작해서 BFS로 돌면서 이동거리 +1 2. 시간복잡도 - O(V + E) - V : 300000 - E : 1000000 3. 자료.. [BOJ] 2667. 단지번호붙이기 https://www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net 1. 해결방법 """ 1. 아이디어 - 2차원 배열 : int[][] - 방문 기록 : bool[][] - BFS를 돌면서 지도 각 단지의 연결된 아파트의 수를 구함. - 구한 아파트 수를 오름차순으로 출력. : sort() 2. 시간복잡도 - O(V + E) - V : 25 X 25 = 25^2 - E : 4 X 25 X 25 = 4 X 25^2 3. 자료구조 - BFS(Queue) - 2차원 배.. [이코테] 미로 탈출 (BFS) / [BOJ] 2178. 미로 탈출 1. 해결 방법 """ 1. 아이디어 - 2차원 배열을 사용 - BFS를 돌면서 한번 움직일 때마다 +1, 입구에서 출구까지의 거리를 계산 후 최소 이동 거리를 갱신 - 출잘점 (1, 1)에서 목적지 (n, m)까지 이동하는데 해당 노드에 처음 도달한 경우(1일 때) 모든 방향의 노드 값을 +1 해준다. 2. 시간복잡도 - O(V + E) - V : m X n = 200 X 200 = 40000 - E : 4V = 4 * 40000 3. 자료구조 - 이차원 배열 : int[][] - 방문 기록 : bool[][] - BFS(Queue) """ 노드를 이동할 때마다 노드의 값에 +1을 해주면 된다. 단, 상하좌우를 판단해서 이동할 수 있는 경로가 다수일 경우에는 모든 방향에 +1 처리를 해준다. 그러면 결.. [이코테] 음료수 얼려 먹기 (BFS) 1. 해결 방법 """ 1. 아이디어 - 2중 for문 => int[][] - BFS를 돌면서 +1, 생성되는 아이스크림의 개수를 구함 2. 시간복잡도 - O(V + E) - V : m X n = 1000 X 1000 = 1000000 - E : 4V = 4 * 1000000 3. 자료구조 - 얼음 틀 2차원 배열 : int[][] - 방문 : bool[][] - BFS(Queue) """ 그래프 형태이기 때문에 2차원 배열을 사용해야 한다. 마찬가지로 방문 기록을 남겨야 하기 때문에 bool 형태의 2차원 배열을 추가적으로 구현하였다. 하나의 노드(vertex)를 방문하면 그 노드와 연관되어있는 자식 노드를 추가적으로 방문하여 큐에 넣는다. 이런식으로 하나의 얼음 틀을 만들때 까지 방문하다가 연결이 끊.. [BOJ] 1926. 그림 https://www.acmicpc.net/problem/1926 1926번: 그림 어떤 큰 도화지에 그림이 그려져 있을 때, 그 그림의 개수와, 그 그림 중 넓이가 가장 넓은 것의 넓이를 출력하여라. 단, 그림이라는 것은 1로 연결된 것을 한 그림이라고 정의하자. 가로나 세로 www.acmicpc.net 1. 해결 방법 1. 아이디어 - 2중 for => 값 1 & 방문 x => BFS - BFS 돌면서 그림 개수 + 1, 최댓값을 갱신 2. 시간복잡도 (한번에 2억개를 실행) - BFS : O(V + E) - V : m(최대 500) X n(최대 500) = 250000 - E : 대략 V X 4(넉넉히) = 4 * 250000 - O : 5 * 250000 시간복잡도 문제 없음 3... 이전 1 ··· 19 20 21 22 다음