문제 탐색

코드 설계

  1. Input (배추들의 위치) Adjacency Matrix (2차원 배열)에 표시
  2. 방문한 위치를 visited 2차원 배열에 표시
  3. (0, 0)부터 배추가 있는지, 이미 방문했던 좌표 (이미 방문했던 배추 그룹) 인지를 판별하고
    • 배추가 있고, 새로 방문한 곳이라면 인접한 배추들을 BFS로 방문.
    • 방문한 위치를 visited에 표시
    • 인접한 배추를 다 방문했다면 탐색 종료.
  4. 새로운 배추 그룹을 찾는다.
    • 해당 그룹의 start 지점을 발견하면 지렁이를 한 마리 추가한다.

구현

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

public class Main {
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());
        StringTokenizer st;
        while(T-- > 0){
            // Input
            st = new StringTokenizer(br.readLine());
            int M = Integer.parseInt(st.nextToken());
            int N = Integer.parseInt(st.nextToken());
            int K = Integer.parseInt(st.nextToken());

            boolean[][] g = new boolean[M][N];
            boolean[][] visited = new boolean[M][N];
            while(K-- > 0){
                st = new StringTokenizer(br.readLine());
                int x = Integer.parseInt(st.nextToken());
                int y = Integer.parseInt(st.nextToken());
                g[x][y] = true;
            }

            // Traversal
            int result = 0;
            int[] dx = new int[] { 0, 1, 0, -1};
            int[] dy = new int[] { 1, 0, -1, 0};

            for(int i = 0; i < M; i++){
                for(int j = 0; j < N; j++){
                    // 시작 점
                    if(g[i][j] == false || visited[i][j]) continue;
                    else result++;

                    // BFS 시작
                    Queue<int[]> q = new ArrayDeque<>(); 
                    q.add(new int[] {i, j});
                    visited[i][j] = true; // 시작점 방문
                    
                    while(!q.isEmpty()){
                        int[] current = q.poll();
                        for(int dir = 0; dir < 4; dir++){
                            int currentX = current[0] + dx[dir];
                            int currentY = current[1] + dy[dir];
                            if(currentX < 0 || currentY < 0 || currentX >= M || currentY >= N) continue;
                            if(!g[currentX][currentY] || visited[currentX][currentY]) continue;
                            visited[currentX][currentY] = true; // enque할 때 visited
                            q.add(new int[] {currentX, currentY});
                        }
                    }
                }
            }
            System.out.println(result);
        }
    }
}

배움

  • 12%에서 메모리 초과가 났었다.
    • 새 좌표에 방문하는 시점 (디큐할 때 (poll)) 에 visited 처리해주고 있었는데 중복 enque가 발생했었다.
    • 동일한 좌표가 큐에 여러번 들어가면 최악의 경우 N번 이상 중복 방문하게 된다.
    • 이러한 이유로 중복 인큐를 방지하기 위해 큐에서 꺼낸 시점이 아닌, 큐에 넣기 전에 visited[currentX][currentY] = true로 수정했다.
  • 👀 다른 사람의 DFS 풀이 https://chaerim1001.tistory.com/97