[Algorithm] 99클럽 코테 스터디 8일차 TIL BOJ 2667

문제

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

풀이

문제 분석

• 단순한 그래프 탐색 문제였고 나는 dfs로 해결해보았다

1. 입력을 받는다
2. 아직 한번도 방문하지 않았고 집이 있는 위치부터 dfs 탐색을 시작한다
 - 아직 한번도 방문하지 않았고 집이 있는 위치라면 방문 여부 업데이트 및 count를 증가하고, 상하좌우에 대하여 dfs를 진행한다
3. for문 내부에서 2번 조건을 만족하여 if문 안에 들어가게 되면 그 순간 하나의 단지가 생성되므로 villageCount를 증가하고 dfs를 통해 계산된 count를 eachHomeCount에 저장한다
4. eachHomeCount 리스트를 오름차순으로 정렬한다
5. 단지의 총 개수와 각 단지에 포함된 집의 개수를 오름차순으로 출력한다

코드

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

public class Main {
    private static int N = 0;
    private static boolean[][] visited;
    private static int[][] village;
    private static int count = 0;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        visited = new boolean[N][N];
        village = new int[N][N];

        for(int i=0 ; i<N; i++) {
            String line = br.readLine();
            for(int j=0; j<N; j++) {
                village[i][j] = line.charAt(j) - '0';
            }
        }

        int villageCount = 0;
        ArrayList<Integer> eachHomeCount = new ArrayList<>();

        for(int i=0 ; i<N; i++) {
            for(int j=0; j<N; j++) {
                if(!visited[i][j] && village[i][j]==1) {
                    villageCount++;
                    count = 0;
                    dfs(i, j);
                    eachHomeCount.add(count);
                }
            }
        }

        System.out.println(villageCount);
        eachHomeCount.sort(Comparator.naturalOrder());
        eachHomeCount.forEach(System.out::println);
    }

    private static void dfs(int i, int j) {
        if(!visited[i][j] && village[i][j] == 1) {
            count++;
            visited[i][j] = true;
            if(j+1<N)
                dfs(i, j+1);
            if(j-1>=0)
                dfs(i, j-1);
            if(i-1>=0)
                dfs(i-1, j);
            if(i+1<N)
                dfs(i+1, j);
        }
    }

}

TIL

• 방향과 관련된 문제가 나올 때에는 배열을 이용할 수 있기 때문에 간단히 정리해보려한다
• 보통 다음과 같이 많이 표시하고 사용한다 (예시 코드는 내 코드의 dfs 부분에서 수정할 수 있도록 작성하였다)

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

for(int k = 0; k < 4; k++) {
	int nx = i + dx[k];
	int ny = j + dy[k];
			
	if(0 <= nx && nx < N && 0 <= ny && ny < N && village[nx][ny] == '1' && !visited[nx][ny])
		dfs(nx, ny);
}