알고리즘 스터디 5주차 1

2606

• 알고리즘 : 그래프 탐색
• 난이도 : 실버3

문제

2606

접근

• 노드로 연결된 그래프 문제이다.
  • 이번 문제는 1번 컴퓨터의 연결된 노드의 총 갯수를 구하면된다.
  • 만약 좀 더 생각한다면 각각 1번 컴퓨터와 7번 컴퓨터가 감염 시킨 갯수를 구할 수 도 있겠지?
  • 이번 문제에서는 1번 컴퓨터 기준으로 생각하면 된다.
  • BFS와 DFS 둘 중 아무거나 풀어도 된다
    • 컴퓨터의 갯수가 정확히 주어지지 않아 제한사항이 없을 것이다.

가정

• BFS로 풀기 위해서 Queue를 만든다.
• ArrayList를 이용하여 푸는데 갯수만 구하면 되기에 List로 들어온 순서를 고려할 필요가 없다.
  • 만약 정확히 순서도 구해야되는 문제라면 ArrayList에 담긴 노드들의 순서를 다시 정렬해주고 BFS로 탐색해야한다.

풀어보기

public class Main {
	static int computerCount; //컴퓨터의 갯수
	static int N; // 노드를 연결할 갯수
	static ArrayList<Integer>[] A; // 노드를 담는 배열
	static boolean[] visited; // 방문여부 확인
	static int count; // 감염시킨 갯수
	public static void main(String[] args) throws IOException {
		BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
		computerCount = Integer.parseInt(reader.readLine());
		N = Integer.parseInt(reader.readLine());
		A = new ArrayList[computerCount+1];

		// 해당 노드들의 배열리스트를 초기화 해주어야한다.
		for(int i = 1; i <= computerCount; i++) {
			A[i] = new ArrayList<>();
		}
        
		for(int i = 1; i < N+1; i++){
			String[] line = reader.readLine().split(" ");
			int start = Integer.parseInt(line[0]);
			int end = Integer.parseInt(line[1]);
            // 기준 노드는 배열의 인덱스, 연결된 타겟 노드는 리스트로 담아낸다. 순서가 없기 때문에 양방향을 모두 연결한다.
			A[start].add(end);
			A[end].add(start);
		}
        // 배열의 탐색 여부 확인 
		visited = new boolean[computerCount+1];
        // 기준 노드인 1부터 시작
		bfs(1);
		System.out.println(count);
	}
	public static void bfs(int start){
    // 큐로 구현 한다.
		Queue<Integer> queue = new LinkedList<>();
	// 기준 노드를 먼저 담는다.
		queue.add(start);
        // 기준 노드는 방문한 것으로 한다.
		visited[start] = true;
		while(!queue.isEmpty()){
        // 노드를 뽑아 검사한다. 
			int cur = queue.poll();
			if(cur != 1){
			// 뽑을 때마다 갯수를 탐색, 1을 제외하고 감염시킨 컴퓨터 갯수 
            count++;
			}
            // 해당 시작 노드의 리스트를 확인하고 방문여부를 체크
			for(int i : A[cur]){
            // 방문하지 않았다면 
				if(!visited[i]){
                // 방문으로 체크하고 타겟 노드를 시작 노드로 만들기 위해 큐에 담는다.
					visited[i] = true;
					queue.add(i);
				}
			}
		}
	}
}

시행착오

• 없음

참고자료

BFS와 DFS 쉽게 구현하기

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {
	static boolean visited[];
	static ArrayList<Integer>[] A;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String [] first = br.readLine().split(" ");
		int N = Integer.parseInt(first[0]);
		int M = Integer.parseInt(first[1]);
		int start = Integer.parseInt(first[2]);
		A = new ArrayList[N+1];
		for(int i = 1; i <= N; i++) {
			A[i] = new ArrayList<Integer>();
		}
		for(int i = 0; i< M; i++) {
			String[] line = br.readLine().split(" ");
			int S = Integer.parseInt(line[0]);
			int E = Integer.parseInt(line[1]);
			A[S].add(E);
			A[E].add(S);
		}

		for(int i = 1; i<=N; i++) {
			Collections.sort(A[i]);
		}
		visited = new boolean[N+1];
		DFS(start);
		System.out.println();
		visited = new boolean[N+1];
		BFS(start);
		System.out.println();

	}
	public static void DFS(int Node) {
		System.out.print(Node +" ");
		visited[Node] = true;
		for(int i : A[Node]) {
			if(!visited[i]) {
				DFS(i);
			}
		}
	}

	private static void BFS(int Node) {
		Queue<Integer> queue = new LinkedList<>();
		visited[Node] = true;
		queue.add(Node);
		while(!queue.isEmpty()){
			int new_node = queue.poll();
		System.out.print(new_node +" ");
			for(int i : A[new_node]){
				if(!visited[i]){
					visited[i] = true;
					queue.add(i);
				}
			}
		}
	}

}