백준 1012번 바로가기

---

📌자바

자바에서의 큐(Queue) 자료구조 사용법을 배웠다.

자바에서는 LinkedList를 이용하여 큐를 구현한다.

import java.util.LinkedList;
import java.util.Queue;

Queue<Integer> que = new LinkedList<>();

Queue와 LinkedList 라이브러리를 모두 import 해주고 선언한다.

물론 이 문제를 풀 땐, 조금 더 응용해서 정수형 큐가 아닌, 리스트형 큐를 선언해주었다.

Queue<List<Integer>> que = new LinkedList<>();

정수형 리스트를 인자로 사용하는 큐를 선언했다.

내가 익숙한 파이썬에서는 또 파이썬 이야기다

from collections import deque

que = deque((a, b, c))

이렇게 그냥 선언만 해주어도 튜플을 넣든 배열을 넣든 통일만 해주면 상관이 없었는데, 파이썬 이외의 다른 언어들은 형태를 선언해주어야 하기 때문에 처음엔 번거로웠다.

---

📌1012번 유기농 배추

당연하게도 파이썬으로 푼 문제이고, BFS는 익숙해져있기 때문에 로직을 떠올리는건 쉬웠지만 구현이 어려웠다.

해당 문제에서는 이미 탐색했는지를 확인하는 그래프인 visited 배열을 BFS 함수 내에서 수정하고(탐색 완료 표기) 해당 배열을 Main문에서도 확인해야 했다.

그래서 visited 배열을 전역에 선언하고, testCase가 바뀔 때 마다 초기화 해주면서 풀었다.

static int[][] visited;
visited = new int[m][n];

코드전문

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

public class Main {

    static int[] dx = {0, -1, 0, 1};
    static int[] dy = {-1, 0, 1, 0};
    static int[][] graph;
    static int[][] visited;

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

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        Scanner sc = new Scanner(System.in);

        int t = sc.nextInt();

        for (int testCase = 0; testCase < t; testCase++) {
            int m = sc.nextInt();
            int n = sc.nextInt();
            int k = sc.nextInt();

            graph = new int[m][n]; // 0으로 자동 초기화

            for (int i = 0; i < k; i++) {
                int graphX = sc.nextInt();
                int graphY = sc.nextInt();

                graph[graphX][graphY] = 1;
            }

            int answer = 0;
            visited = new int[m][n];

            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    if (graph[i][j] == 1 && visited[i][j] == 0) {
                        bfs(i, j, m, n);
                        answer++;
                    }
                }
            }
            System.out.println(answer);
        }
    }

    private static void bfs(int startx, int starty, int m, int n) {

        Queue<List<Integer>> que = new LinkedList<>();
        que.add(List.of(startx, starty));

        while (!que.isEmpty()) {
            List<Integer> nowGraph = que.poll();
            for (int i = 0; i < 4; i++) {
                int nowX = nowGraph.get(0) + dx[i];
                int nowY = nowGraph.get(1) + dy[i];

                if (m > nowX && nowX >= 0 && n > nowY && nowY >= 0) {
                    if (visited[nowX][nowY] == 0 && graph[nowX][nowY] == 1) {
                        visited[nowX][nowY] = 1;
                        que.add(List.of(nowX, nowY));
                    }
                }
            }
        }
    }
}