[백준] S2606

https://www.acmicpc.net/problem/2606

2606번: 바이러스

 

# 아이디어

간선의 정보를 2차원 배열에 저장하고 visited라는 1차원 배열을 통해 정점을 지났는지 아닌지 판별하여 dfs 탐색한다.

이를 통해, 네트워크 망이 연결된 컴퓨터를 찾을 수 있음!!!

이전에 풀었던 dfs와 bfs 문제와 아주 유사함!!

이번에는 정말로 코드를 다 이해한듯?? 블로그 안 보고 품 😎

 

# 오답

Sol 1.

cnt의 값이 -1로 출력됨.

package baekjoon;

import java.util.Scanner;

public class S2606 {

	public static void dfs(int start, int[][] map, int[] visited, int cnt) {
		if (visited[start] == 1) {
			return;
		}
		visited[start] = 1;
		cnt++;

		for (int i = 1; i < map.length; i++) {
			if (map[start][i] == 1 && visited[i] == 0) {
				dfs(i, map, visited, cnt);
			}
		}

	}

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		int vertex, edge;
		vertex = sc.nextInt();
		edge = sc.nextInt();

		int[][] map = new int[vertex + 1][vertex + 1];
		int[] visited = new int[vertex + 1];

		for (int i = 0; i < edge; i++) {
			int left = sc.nextInt();
			int right = sc.nextInt();
			map[left][right] = map[right][left] = 1;
		}

		int cnt = 0;
		dfs(1, map, visited, cnt);
		
		System.out.println(--cnt);
		
		sc.close();

	}

}

 

=> call by reference와 call by value가 또 헷갈리기 시작한다...;;;

 

Sol 2.

cnt를 static 변수로 선언하니 값을 올바르게 나온다!

package baekjoon;

import java.util.Scanner;

public class S2606 {
	
	public static int cnt = 0;

	public static void dfs(int start, int[][] map, int[] visited) {
		if (visited[start] == 1) {
			return;
		}
		visited[start] = 1;
		cnt++;

		for (int i = 1; i < map.length; i++) {
			if (map[start][i] == 1 && visited[i] == 0) {
				dfs(i, map, visited);
			}
		}

	}

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		int vertex, edge;
		vertex = sc.nextInt();
		edge = sc.nextInt();

		int[][] map = new int[vertex + 1][vertex + 1];
		int[] visited = new int[vertex + 1];

		for (int i = 0; i < edge; i++) {
			int left = sc.nextInt();
			int right = sc.nextInt();
			map[left][right] = map[right][left] = 1;
		}

		
		dfs(1, map, visited);
		
		System.out.println(--cnt);
		
		sc.close();

	}

}

 

 

💯💯💯

static 변수를 사용하는 것이 코테에 영향을 끼치는지 궁금하네??

※ stack을 이용하는 DFS 풀이, BFS 풀이 해보기!!!