[JAVA]BOJ(백준) - 단지번호붙이기 - 2667

- 문제 내용

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

2667번: 단지번호붙이기

---

- 문제 접근 방법

• 입력받은 값을 2차원배열에 넣어 하나씩 0인지 1인지를 확인하기
• 2차원배열의 방문배열을 만들어서 방문여부도 함께 확인하기
• 확인된 집으로부터 dfs로 상하좌우를 돌면서 집이 있는지 없는지 확인하기
  1. 집이 없다면 해당 dfs를 끝낸다.
  2. 집이 있다면 다음 dfs를 호출한다.

이렇게 문제를 접근하면서 필요한것들 -> 집세주는 변수, 단지수 알려주는 변수, 방문배열 까지는 생각 했는데 상하좌우를 어떻게 해줘야 할지 답이 안나와서 다른분의 코드를 참고했다.

보고나니 백준의 N-Queen문제를 떠올리면 되는문제 여서 허무했던ㅠㅠ.. 여튼 풀이를 보자ㅎ

참고로 풀이에서 좌표라고 말하는건 인덱스라 생각하면됨.

---

- 풀이

• 선언값들

	static int N; // 입력값
	static int[][] danji; // 입력되는 2차원배열 넣을 공간(지도)
	static boolean[][] check; // 방문 배열
	static int houseCnt; // 단지하나에 있는 집들의 수
	static ArrayList<Integer> danjiCnt; // 단지 수
	static int[] x = {0, 0, -1, 1}; // 상하좌우
	static int[] y = {-1, 1, 0, 0}; // 상하좌우

 

• main 부분

public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		danji = new int[N][N]; //단지(지도)의 크기는 N의 값에 의해 결정
		check = new boolean[N][N]; //방문배열 크기도 마찬가지
		danjiCnt = new ArrayList<Integer>();
		
		for(int i=0; i<N; i++) { // 들어오는 입력값을 단지배열에 넣기 위한 작업
			StringTokenizer st = new StringTokenizer(br.readLine());
			String a = st.nextToken();
			for(int j=0; j<N; j++) {
				danji[i][j] = Integer.parseInt(a.substring(j, j+1));
			}
		}
		
		new BOJ_2667().solution();
		
		System.out.println(danjiCnt.size()); // 요소값들은 단지 하나에 있는 집들의 수가 되고 size가 단지 수가 됨.
		Collections.sort(danjiCnt); // list 오름차순 정렬
		for(int a:danjiCnt) {
			System.out.println(a); // 출력
		}
	}

 

• 함수 부분

	public void solution() {
		for(int i=0; i<N; i++) {
			for(int j=0; j<N; j++) {
				
				//이 조건에 걸리면 일단 집하나를 찾은거. 그리고 여기부터 상하좌우를 보면서 
				//이어진 집들을 쭉이어서 하나의 단지로 만들꺼임.
				if(danji[i][j]==1 && !check[i][j]) {
					houseCnt=1; //일단 집하나 찾은거라 houseCnt를 1증가 시켜줌.
					dfs(i,j); //첫번째로 찾은집과 이어진 집들 찾기위한 dfs 호출
					
					//dfs 끝나면 dfs에서 houseCnt++ 했던거 danjiCnt에 추가.
					//danjiCnt에 추가하면 단지가 1개 추가 된거고 단지 1개에 있는 집들의 수는 요소의 값이 됨.
					danjiCnt.add(houseCnt);
					
				}//if
			}//for
		}//for
	}//solution
	
	public void dfs(int v1, int v2) {
		check[v1][v2]=true; //방문된 집은 true처리
		
		for(int i=0; i<4; i++) { // 4번(상하좌우)을 돌면서 이어진 집이 있는지 확인하기 위한 작업
			
			int dx = v1 + x[i]; // 기존 집 좌표에 +1, -1을 해줘서 좌표 변경   
			int dy = v2 + y[i]; // 기존 집 좌표에 +1, -1을 해줘서 좌표 변경
            
			// 변경된 좌표 dx, dy는 지도크기에 벗어나면 안됨. 
			// 그리고 좌표(인덱스)값은 무조건 +가 나와야됨.
			if(dx>=0 && dy>=0 && dx<N && dy<N) { 
				if(danji[dx][dy]==1 && !check[dx][dy]) {// 변경된 좌표에 집이 있고 방문안한 집일때 다시 dfs 호출하도록 하는 조건. 
					dfs(dx,dy); // 변경된 좌표의 집부터 다시 반복 시작.
					houseCnt++; // 방문끝난 집이라 houseCnt 증가
				}//if
			}//if
		}//for
	}//dfs

 

• 전체코드

package org.boj.dfs.bfs;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.StringTokenizer;

public class BOJ_2667 {
	
	static int N; // 입력값
	static int[][] danji; // 입력되는 2차원배열 넣을 공간(지도)
	static boolean[][] check; // 방문 배열
	static int houseCnt; // 단지하나에 있는 집들의 수
	static ArrayList<Integer> danjiCnt; // 단지 수
	static int[] x = {0, 0, -1, 1}; // 상하좌우
	static int[] y = {-1, 1, 0, 0}; // 상하좌우
	
	public void solution() {
		for(int i=0; i<N; i++) {
			for(int j=0; j<N; j++) {
				
				//이 조건에 걸리면 일단 집하나를 찾은거. 그리고 여기부터 상하좌우를 보면서 
				//이어진 집들을 쭉이어서 하나의 단지로 만들꺼임.
				if(danji[i][j]==1 && !check[i][j]) {
					houseCnt=1; //일단 집하나 찾은거라 houseCnt를 1증가 시켜줌.
					dfs(i,j); //첫번째로 찾은집과 이어진 집들 찾기위한 dfs 호출
					
					//dfs 끝나면 dfs에서 houseCnt++ 했던거 danjiCnt에 추가.
					//danjiCnt에 추가하면 단지가 1개 추가 된거고 단지 1개에 있는 집들의 수는 요소의 값이 됨.
					danjiCnt.add(houseCnt);
					
				}//if
			}//for
		}//for
	}//solution
	
	public void dfs(int v1, int v2) {
		check[v1][v2]=true; //방문된 집은 true처리
		
		for(int i=0; i<4; i++) { // 4번(상하좌우)을 돌면서 이어진 집이 있는지 확인하기 위한 작업
			
			int dx = v1 + x[i]; // 기존 집 좌표에 +1, -1을 해줘서 좌표 변경   
			int dy = v2 + y[i]; // 기존 집 좌표에 +1, -1을 해줘서 좌표 변경
            
			// 변경된 좌표 dx, dy는 지도크기에 벗어나면 안됨. 
			// 그리고 좌표(인덱스)값은 무조건 +가 나와야됨.
			if(dx>=0 && dy>=0 && dx<N && dy<N) { 
				if(danji[dx][dy]==1 && !check[dx][dy]) {// 변경된 좌표에 집이 있고 방문안한 집일때 다시 dfs 호출하도록 하는 조건. 
					dfs(dx,dy); // 변경된 좌표의 집부터 다시 반복 시작.
					houseCnt++; // 방문끝난 집이라 houseCnt 증가
				}//if
			}//if
		}//for
	}//dfs
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		danji = new int[N][N]; //단지(지도)의 크기는 N의 값에 의해 결정
		check = new boolean[N][N]; //방문배열 크기도 마찬가지
		danjiCnt = new ArrayList<Integer>();
		
		for(int i=0; i<N; i++) { // 들어오는 입력값을 단지배열에 넣기 위한 작업
			StringTokenizer st = new StringTokenizer(br.readLine());
			String a = st.nextToken();
			for(int j=0; j<N; j++) {
				danji[i][j] = Integer.parseInt(a.substring(j, j+1));
			}
		}
		
		new BOJ_2667().solution();
		
		System.out.println(danjiCnt.size()); // 요소값들은 단지 하나에 있는 집들의 수가 되고 size가 단지 수가 됨.
		Collections.sort(danjiCnt); // list 오름차순 정렬
		for(int a:danjiCnt) {
			System.out.println(a); // 출력
		}
	}
}

참고로 dfs 함수 부분에서 dx, dy를 만들어줄때 x와 y를 바꿔도 여기선 상관없긴 하다

 

---

- 마치며

풀고나면 언제나 간단하지만 내 기준에선 어려웠던 문제라고 생각한다. 생각했던 시간도 길었고 무엇보다 상하좌우 탐색에 대해 어떻게 해야할지 몰랐기 때문인거 같다ㅠ

N Queen문제를 복습 해야할듯!