백준 2667번
https://www.acmicpc.net/problem/2667
문제
<그림 1>과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여기서 연결되었다는 것은 어떤 집이 좌우, 혹은 아래위로 다른 집이 있는 경우를 말한다. 대각선상에 집이 있는 경우는 연결된 것이 아니다. <그림 2>는 <그림 1>을 단지별로 번호를 붙인 것이다. 지도를 입력하여 단지수를 출력하고, 각 단지에 속하는 집의 수를 오름차순으로 정렬하여 출력하는 프로그램을 작성하시오.
입력
첫 번째 줄에는 지도의 크기 N(정사각형이므로 가로와 세로의 크기는 같으며 5≤N≤25)이 입력되고, 그 다음 N줄에는 각각 N개의 자료(0혹은 1)가 입력된다.
출력
첫 번째 줄에는 총 단지수를 출력하시오. 그리고 각 단지내 집의 수를 오름차순으로 정렬하여 한 줄에 하나씩 출력하시오.
예제 입력
7
0110100
0110101
1110101
0000111
0100000
0111110
0111000예제 출력
3
7
8
9생각하기
오랜만에 풀어보는 DFS/BFS문제.. 과연 풀 수 있을까? 생각했지만 너무 쉽게 성공해버려서 기분이 좋았다.
다른 특이점 없이 DFS의 개념만 알고 있다면 쉽게 풀 수 있는 문제였다.
동작
static int arr[][];
static boolean visit[][];
static int dirX[] = {0, 0, -1, 1};
static int dirY[] = {-1, 1, 0, 0};
static int count = 0, number = 0;
static int nowX, nowY, N;DFS가 아무래도 재귀의 방법을 사용하다 보니 static, 정적 변수를 사용할 일이 많다.
그래서 변수를 꽤 많이 만들었다.
dirX와 dirY는 단지 번호를 붙일 때, 대각선을 제외한 상 하 좌 우로 붙어있는 단지에 번호를 부여한다고 했으니,
dirX는 상 하 좌 우 에서 좌 우를 판단하도록 하고,
dirY는 상 하 좌 우 에서 상 하의 범위를 판단 할 수 있도록 배열을 만들었다.
이 배열이 왜 필요한가 생각할 수 있다.
dirX로 예를 들어 설명을 하자면 왼쪽으로 가려면 기준점에서 -1을 해야되고 오른쪽으로 가려면 +1을 해야되기 때문에 저런 배열이 필요하다 생각하면 된다.
nowX 와 nowY는 범위를 계산한 좌표를 담을 변수이다.
N = Integer.parseInt(br.readLine());
arr = new int[N][N];
visit = new boolean[N][N];
for(int i=0; i<N; i++) {
String str = br.readLine();
for(int j=0; j<N; j++) {
arr[i][j] = Character.getNumericValue(str.charAt(j));
}
}이 부분은 input을 배열로 만들어주는 부분이다.
for(int i=0; i<N; i++) {
for(int j=0; j<N; j++) {
if(visit[i][j] == false && arr[i][j] == 1) {
count = 0;
number++;
DFS(i, j);
list.add(count);
}
}
}DFS()는 연결된 1을 따라서만 쭉 가기 때문에 모든 면에 0이 있으면 더 이상 갈 수 없다고 판단해서 메소드가 종료된다. 그렇기 때문에 전체 배열을 탐색하면서, 방문하지 않았고, arr에서 1인 곳을 만날경우 다시 DFS() 메소드가 실행되도록 하면 arr 전체를 탐색할 수 있다.
list는 각 단지의 집의 숫자를 저장하기 위해 만들어 두었다.
static void DFS(int x, int y) {
visit[x][y] = true;
arr[x][y] = number;
count ++;
for(int i=0; i<4; i++) {
nowX = dirX[i] + x;
nowY = dirY[i] + y;
if(Range_check() && visit[nowX][nowY] == false && arr[nowX][nowY] == 1) {
visit[nowX][nowY] = true;
arr[nowX][nowY] = number;
DFS(nowX, nowY);
}
}
} // End of DFSDFS() 과정은 위에서 설명한 것의 연결이다
arr이 1이면서 방문하지 않은 곳일 경우 실행되어
실행되는 순간 방문함을 표시하기 위해 visit[x][y] = true 처리를 해주고 단지번호 부여를 위해 arr[x][y] = number;를 넣어준다.
nowX = dirX[i] + x;
nowY = dirY[i] + y;이제 여기서 범위에 맞는 값을 계산해서 nowX 와 nowY를 저장한다
이후 Range_check() 메소드를 실행해서 범위조건에 true일 경우에만
방문 여부를 true로 바꿔주고, 다시 단지번호를 부여해준다.
이 과정을 반복하면 문제를 해결 할 수 있다.
코드
import java.util.*; import java.io.*; public class Main { static int arr[][]; static boolean visit[][]; static int dirX[] = {0, 0, -1, 1}; static int dirY[] = {-1, 1, 0, 0}; static int count = 0, number = 0; static int nowX, nowY, N; public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out)); List<Integer> list = new ArrayList<>(); N = Integer.parseInt(br.readLine()); arr = new int[N][N]; visit = new boolean[N][N]; for(int i=0; i<N; i++) { String str = br.readLine(); for(int j=0; j<N; j++) { arr[i][j] = Character.getNumericValue(str.charAt(j)); } } for(int i=0; i<N; i++) { for(int j=0; j<N; j++) { if(visit[i][j] == false && arr[i][j] == 1) { count = 0; number++; DFS(i, j); list.add(count); } } } Collections.sort(list); bw.append(number + "\n"); for(int num : list) { bw.append(num + "\n"); } bw.flush(); bw.close(); } // End of main static void DFS(int x, int y) { visit[x][y] = true; arr[x][y] = number; count ++; for(int i=0; i<4; i++) { nowX = dirX[i] + x; nowY = dirY[i] + y; if(Range_check() && visit[nowX][nowY] == false && arr[nowX][nowY] == 1) { visit[nowX][nowY] = true; arr[nowX][nowY] = number; DFS(nowX, nowY); } } } // End of DFS static boolean Range_check() { return (nowX >= 0 && nowX < N && nowY >= 0 && nowY < N); } // End of Range_check } // End of class
