(#2606 Java) 바이러스

 

ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ 진짜 짜증나 죽는 줄 알았다... 분명 내 로컬에서는 답이 잘 나오는데, 왜 계속 이러는 거지 했는데, 진짜 어이없는 실수였던 것,,, i가 곧 node 번호인 걸 잊고 그냥 습관처럼 0부터 했다가 난 실패 메세지였다.

1번부터 방문하기 때문에 1부터 넣어주어야 한다..

 

문제 해결

 

이것도 DFS/BFS 두 가지 방법으로 풀 수 있는데 나는 DFS에서 재귀 방법을 선택했다.

DFS/BFS 문제를 풀기 위해 필요한 것들을 세팅해주자.

최종적으로 웜 바이러스에 걸리게 되는 컴퓨터의 수를 출력해주어야 하므로 추가로 count 변수도 만들어주자.

static int N, E; //컴퓨터 수, 연결된 선의 개수
static int[][] Graph;
static boolean[] Visited; //방문 여부
static int count = 0;

 

dfs 함수를 만들어주자. 내가 자꾸 틀린 이유가 여기있다. 문제에서 1번부터 컴퓨터 번호가 매겨진다고 했으니 i는 0이 아닌 1부터 시작해야한다. (0번 노드는 없음) 그렇기에 당연히 N+1까지로 범위를 잡아주었다.

이제부터 전형적인 dfs 코드이다. 방문을 하지 않았고, 간선으로 연결되어 있으면 dfs를 호출해주고, 여기에서는 count를 증가시켜주어야 한다.

static void dfs(int node) {
    Visited[node] = true;

    for(int i = 1; i < N+1; i++) {
        if(!Visited[i] && Graph[node][i] == 1) { //아직 방문하지 않았고, 연결되어 있으면 dfs 호출
            dfs(i);
            count++;
        }
    }
}

 

메인 함수는 다른 dfs 문제들과 거의 동일하니 최종코드에서만 확인하는 것으로 하자.

 

최종 코드

 

 

package org.example.DfsBfs;

import java.util.Scanner;

public class Virus {
    static int N, E; //컴퓨터 수, 연결된 선의 개수
    static int[][] Graph;
    static boolean[] Visited; //방문 여부
    static int count = 0;

    static void dfs(int node) {
        Visited[node] = true;

        for(int i = 1; i < N+1; i++) {
            if(!Visited[i] && Graph[node][i] == 1) { //아직 방문하지 않았고, 연결되어 있으면 dfs 호출
                dfs(i);
                count++;
            }
        }
    }

    public static void main(String[] args) throws Exception{

        Scanner in = new Scanner(System.in);
        N = in.nextInt();
        E = in.nextInt();
        Graph = new int[N+1][N+1];
        Visited = new boolean[N+1];

        for(int i = 0; i < E; i++) {
            int u = in.nextInt();
            int v = in.nextInt();
            Graph[u][v] = Graph[v][u] = 1; //연결되어 있으면 1로 표시 (방향성 X)
        }
        dfs(1);
        System.out.println(count);
    }
}