1743번, 2606번 - DFS, BFS

오늘은 실버 고티어 문제 두 문제를 풀었다.

최근 DFS, BFS를 많이 풀다 보니, 푸는 시간도 줄었고, 큰 고민도 하지 않았다.

 

1745번 - 음식물 피하기

문제:

N x M 사이즈의 지도에 음식물이 있는 위치가 K 번 주어진다.

이때 가장 큰 음식물의 크기를 구하여라.

 

풀이:

힌트를 보면 그동안 푼 문제들과 크게 다르지 않다는 것을 알 수 있을 것이다. 특히 아래 문제와 매우 비슷하다.

1303번 - 4방향 탐색(dfs) (tistory.com)

 

과정은 아래와 같다.

1. 저장 시 queue<int[]> 형태에 저장해준다.

2. 모두 저장이 끝난 후, poll() 한 좌표에 이전에 방문한 적이 없다면,
    해당 좌표와 연결된 음식물의 크기를 끝까지 추적하는 함수를 호출한다.

3. queue가 빌 동안 2번 과정을 반복해준다.

 

2번에서 말하는 함수는 아래와 같이 구현했다.

static void maxTrash(int y, int x) {
    sum++;
    visited[y][x] = true;
    for (int i = 0; i < 4; i++) {
        int nextY = y + yMove[i];
        int nextX = x + xMove[i];
        if (nextY >= 0 && nextY < N && nextX >= 0 && nextX < M) {
            if (!visited[nextY][nextX] && map[nextY][nextX] == 1) {
                maxTrash(nextY, nextX);
            }
        }
    }
}

동, 서, 남, 북 방향으로 순차적으로 이동할 수 있게 미리 xMove와 yMove에 이동 방향을 저장해놓는다. 

동, 서, 남, 북 모든 방향에 대해 검사하며, 해당 위치에 검사하지 않은 음식물이 있다면,
그 방향으로 이동하고, 음식물 크기가 1 늘어났다는 것을 기록한다.

 

위와 같은 방식으로 큐에 저장된 좌표를 모두 검사하면 가장 큰 음식물의 크기를 구할 수 있을 것이다.

전체 코드는 아래와 같다.

import java.io.*;
import java.util.*;

public class 음식물피하기_1743번 {

    static int N, M, K;
    static int[][] map;
    static boolean[][] visited;
    static Queue<int[]> queue;
    static int[] xMove = {1, -1, 0, 0};
    static int[] yMove = {0, 0, 1, -1};
    static int max = 0;
    static int sum = 0;

    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        String[] dimensions = br.readLine().split(" ");
        N = Integer.parseInt(dimensions[0]);
        M = Integer.parseInt(dimensions[1]);
        K = Integer.parseInt(dimensions[2]);

        queue = new LinkedList<>();
        map = new int[N][M];
        for (int i = 0; i < K; i++) {
            String[] trash = br.readLine().split(" ");
            int y = Integer.parseInt(trash[0])-1;
            int x = Integer.parseInt(trash[1])-1;
            queue.add(new int[]{y, x});
            map[y][x] = 1;
        }

        visited = new boolean[N][M];
        while (!queue.isEmpty()) {
            int[] road = queue.poll();
            int y = road[0];
            int x = road[1];
            if (!visited[y][x]) {
                maxTrash(y, x);
                max = Math.max(max, sum);
                sum = 0;
            }
        }
        System.out.println(max);
    }

    static void maxTrash(int y, int x) {
        sum++;
        visited[y][x] = true;
        for (int i = 0; i < 4; i++) {
            int nextY = y + yMove[i];
            int nextX = x + xMove[i];
            if (nextY >= 0 && nextY < N && nextX >= 0 && nextX < M) {
                if (!visited[nextY][nextX] && map[nextY][nextX] == 1) {
                    maxTrash(nextY, nextX);
                }
            }
        }
    }
}

 

2606번 - 바이러스

문제:

위와 같은 그래프에서 1번 컴퓨터에 바이러스가 걸렸다.

그렇다면 2, 3, 5, 6번만 바이러스에 걸리고, 1번을 통해 바이러스에 걸린 컴퓨터의 수는 4가 된다.

1번 컴퓨터에 바이러스가 걸렸을 때 1번을 통해 바이러스에 걸리게 되는 컴퓨터의 수를 구하여라.

첫째 줄에는 컴퓨터의 수가, 둘째 줄에는 네트위크 상에서 연결된 컴퓨터 쌍 수가 주어진다.

 

풀이:

네트워크는 양방향 그래프이므로, 입력이 주어졌을 때 양방향으로 저장해야 한다.

이후, 1번에 연결되어 있는 모든 노드를 찾아야 하는데,
이때는 dfs에 비해 다시 되돌아가는 과정이 필요 없는 bfs가 더 빠른 결과를 보일 것이다.

bfs를 이용해 1번과 연결된 모든 노드를 확인하고 중복에 유의하며, 몇 개의 컴퓨터에 감염이 되었는지 확인하면 된다.

아래는 해당 과정을 나타내는 메서드이다.

static void bfs() {
    Queue<Integer> queue = new LinkedList<>();
    queue.add(1);
    visited[1] = true;
    while (!queue.isEmpty()) {
        int now = queue.poll();
        while (!network.get(now).isEmpty()) {
            int next = network.get(now).poll();
            if (!visited[next]) {
                queue.add(next);
                visited[next] = true;
                sum++;
            }
        }
    }
}

 

 

1. queue에 시작점인 1을 넣어주고, 1에 방문했다고 기록해놓는다.
2. queue.poll()을 통해 지금 컴퓨터를 구하고, 해당 컴퓨터와 연결되어 있는 컴퓨터를 모두 queue에 저장해준다.
   2-1. 만일 연결되어 있는 컴퓨터를 체크한 기록이 있다면 무시한다.
   2-2. 해당 컴퓨터를 체크했다고 기록해주며, 숫자도 체크한다.
3. queue가 빌 동안 2번 과정을 반복한다. 

위 과정을 통해 몇 개의 컴퓨터가 바이러스에 감염되어 있는지 알 수있다.

아래는 전체 코드이다. 입력과정에서 양방향으로 저장해야 오류가 발생하지 않을 것이다.

import java.util.*;

public class 바이러스_2606번 {
    static int N, K;
    static List<Queue<Integer>> network;
    static boolean[] visited;
    static int sum = 0;

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

        network = new ArrayList<>();
        for (int i = 0; i < N+1; i++) {
            network.add(new LinkedList<>());
        }
        for (int i = 0; i < K; i++) {
            int x = sc.nextInt();
            int y = sc.nextInt();
            network.get(x).add(y);
            network.get(y).add(x);
        }

        visited = new boolean[N+1];

        bfs();

        System.out.println(sum);
    }

    static void bfs() {
        Queue<Integer> queue = new LinkedList<>();
        queue.add(1);
        visited[1] = true;
        while (!queue.isEmpty()) {
            int now = queue.poll();
            while (!network.get(now).isEmpty()) {
                int next = network.get(now).poll();
                if (!visited[next]) {
                    queue.add(next);
                    visited[next] = true;
                    sum++;
                }
            }
        }
    }
}