문제

문제 바로가기

코드

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

public class Main {

    static int xLen;
    static int yLen;
    static int n;//배추 개수
    static boolean[][] map;
    static boolean[][] visited;
    static int answer = 0;//지렁이 수
    static int cnt = 0;//인접해있는 배추의 개수

    static void dfs(int curX, int curY){

        if(map[curY][curX] == false) return; // 배추가 있는지 확인
        else if(visited[curY][curX] == true) return; // 방문한 곳인지 확인
        //배추가 있고 방문한 곳도 아니라면
        else{
            cnt++;
            visited[curY][curX] = true;
            if(curX+1 < xLen && curY < yLen) dfs(curX+1, curY); // move right
            if(curX < xLen && curY+1 < yLen) dfs(curX, curY+1); // move down
            if(curX < xLen && curY-1 >= 0) dfs(curX, curY-1); // move up
            if(curX-1 >= 0 && curY < yLen) dfs(curX-1, curY); // move left
        }
    }

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

        String str_ans = "";
        int testCase = Integer.parseInt(br.readLine());
        //테스트케이스만큼 실행
        while(testCase > 0){
            testCase--;
            answer = 0;
            StringTokenizer st = new StringTokenizer(br.readLine());
            xLen = Integer.parseInt(st.nextToken());
            yLen = Integer.parseInt(st.nextToken());
            n = Integer.parseInt(st.nextToken());

            map = new boolean[yLen][xLen];
            visited = new boolean[yLen][xLen];

            for(int i = 0; i < n; i++){
                st = new StringTokenizer(br.readLine()); // StringTokenizer는 한번 선언한 것을 다시 쓰면 된다
                int x = Integer.parseInt(st.nextToken());
                int y = Integer.parseInt(st.nextToken());
                map[y][x] = true;
            }

            for(int i = 0; i < xLen; i++){
                for(int j = 0; j < yLen; j++){
                    dfs(i, j);
                    if(cnt > 0) answer++;
                    cnt = 0;
                }
            }
            str_ans += (answer + "\n");
        }
        System.out.println(str_ans);
    }
}

힘들었던 부분

• while문 안의 첫번째 for문에서 br.readline()을 String 참조변수로 설정했을 때
  두번째 testcase에서 멈춰버린다. 왜 그러는지는 모르겠다...😓
  다음부터는 br.readLine()을 String으로 따로 선언하지말고 바로 Stringtokenizer의 인자로 쓰자✔
• 처음 풀 때는 dfs 메서드에서 왜 상하좌우 움직이는 경우를 다 만들어줘야되는지 몰랐다.
  어차피 이중for문에서 (0,0)→(yLen,xLen)으로 순차적으로 탐색할테니 그냥 오른쪽과 밑으로 이동하는 것만 생각하면 될 줄 알았다.
  이것은 나의 큰 실수였다😅
  이중for문은 인접해있는 배추를 알아보기 위해 첫 step으로 접근할 곳을 찾는 것!
  그 후, dfs 메서드에서 그 배추에 인접한 배추로 나아가는 것이다.
  글 쓰면서 생각하니 이중for문에서 그 곳에 배추가 있는지와 방문했던 곳인지를 판별하고 dfs를 호출했으면 더 좋았을 거 같다는 생각이 든다