백준 2667번 ☆

문제

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

2667번: 단지번호붙이기

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;

public class Main2667 {

	static int N;
	static int[][] house; //아파트 지도
	static boolean[][] visited; //방문여부
	static int[] dfsX = {-1, 1, 0, 0}; // 행(좌,우)
	static int[] dfsY = {0, 0, -1, 1}; // 열(상,하)
	static int count; // 단지 내 집의 개수
	static List<Integer> estate = new ArrayList<Integer>(); // 단지
	
	public static int dfs(int x, int y) {
		visited[x][y] = true;
		
		for (int i=0; i<4; i++) {
			int nextX = x + dfsX[i];
			int nextY = y + dfsY[i];
			
			if (nextX >= 0 && nextY >= 0 && nextX < N && nextY < N) {
				if (!visited[nextX][nextY] && house[nextX][nextY] == 1) {
					dfs(nextX, nextY);
					count++;
				}
			}
		}
		
		return count;
		
	}
	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		
		N = sc.nextInt();
		house = new int[N][N];
		visited = new boolean[N][N];
		
		for (int i=0; i<N; i++) {
			String temp = sc.next();
			for (int j=0; j<N; j++) {
				house[i][j] = temp.charAt(j)-'0';
			}
		}
		
		for (int i=0; i<N; i++) {
			for (int j=0; j<N; j++) {
				if (house[i][j] == 1 && !visited[i][j]) {
					count = 1;
					estate.add(dfs(i, j));
				}
			}
		}
		
		Collections.sort(estate);
		System.out.println(estate.size());
		
		for (int i=0; i<estate.size(); i++) {
			System.out.println(estate.get(i));
		}
		
	}
}

1. 시간을 촉박하게 두고 풀다보니 결국 맞추지 못했다. 

 

2. 재귀를 통해 dfs방식으로 접근하는 것은 좋았으나 재귀와 방문탐색의 원리를 제대로 이해하지 못한탓에 해결방법을 얻지 못했다.

 

3. 이전 완전탐색때 재귀를 통해 dfs 방식을 많이 사용해봤기에 익숙해지고 어느정도 이해를 했다고 생각했다. 하지만 이번 문제를 풀며 느낀점은 문제를 조금만 꼬아내도 로직을 형성하는데 많이 헤맨다는 것이다. 즉, 해당 개념에 대한 이해도가 떨어져 같은 유형이어도 문제를 풀어나가지 못한다.

 

4. 제일 많이 헤맸던 부분은 인접한 요소가 '1'인지 파악하는 부분이었다. 해당 부분을 if문안에서만 해결하려다보니 풀리지 않았다. 다른 블로그의 글들을 보니 배열을 활용해서 해결했다. 두번째로 헤맨 부분은 총 단지의 수와 단지 내 집의 개수를 출력하는 부분이었다. 해당 부분은 어떻게 해야할지 전혀 감이 안잡혔다. for문안에서 count를 1로 초기화 시켜주고(즉, 방문하지 않은 부분에서 다시 1을 발견했을 때 새로운 단지가 생성된다는 것으로 볼 수 있다.) dfs함수를 호출해 해당 부분부터 방문하지 않은 부분들에 대해 '0'을 발견할 때까지 재귀를 계속한다.

 

5. 이외에도 여러부분에서 헤맸지만 위 두가지가 이 문제를 해결하는데 가장 결정적인 부분들이었다. 아직 많은 문제를 풀어보지 못해 개념이 덜 익숙한것일 수도 있다. 항상 조급한 마음을 버리고 조금씩이라도 천천히 꾸준하게 나아가자