Ex) 첫 번째 줄에는 총 단지수를 출력하시오. 그리고 각 단지내 집의 수를 오름차순으로 정렬하여 한 줄에 하나씩 출력하시오
- <그림 1>과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다.
- 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다.
- 여기서 연결되었다는 것은 어떤 집이 좌우, 혹은 아래위로 다른 집이 있는 경우를 말한다.
- 대각선상에 집이 있는 경우는 연결된 것이 아니다. <그림 2>는 <그림 1>을 단지별로 번호를 붙인 것이다.
- 지도를 입력하여 단지수를 출력하고, 각 단지에 속하는 집의 수를 오름차순으로 정렬하여 출력하는 프로그램을 작성하시오.
- 첫 번째 줄에는 지도의 크기 N(정사각형이므로 가로와 세로의 크기는 같으며 5≤N≤25)이 입력되고 그 다음 N줄에는 각각 N개의 자료(0혹은 1)가 입력된다.
MySol) 224ms
<hide/>
// 단지번호 붙이기
import java.util.ArrayList;
import java.util.Scanner;
/*
입출력예시
7
0110100
0110101
1110101
0000111
0100000
0111110
0111000
3
7
8
9
*/
public class Practice1 {
static int MAX_COUNT = 100;
static int[][] AdjMat = new int[MAX_COUNT][MAX_COUNT];
static int[][] Visited = new int[MAX_COUNT][MAX_COUNT];
static int Width = 0;
static int[][] DirMat = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
static int idx = 0;
static ArrayList<Integer> result = new ArrayList<>();
static int cnt = 0; // 각 영역의 개수
public static void DFS(int _currRow, int _currCol){
Visited[_currRow][_currCol] = 1;
++cnt;
for(int i = 0; i < 4; ++i){
int nextRow = _currRow + DirMat[i][0];
int nextCol = _currCol + DirMat[i][1];
if( nextRow <= 0 || nextRow > Width ||
nextCol <= 0 || nextCol > Width){
continue;
}
if(AdjMat[nextRow][nextCol] == 1 && Visited[nextRow][nextCol] == 0){ // 같은 단지 내에서 DFS실행
DFS(nextRow, nextCol);
}
}
}
public static void main(String[] args){
Scanner scan = new Scanner(System.in);
Width = scan.nextInt();
for(int i = 1; i <= Width; ++i){
String str = scan.next();
for(int j = 1; j <= Width; ++j){
AdjMat[i][j] = str.charAt(j - 1) - 48;
}
}
/*
인접행렬 확인
for(int i = 1; i <= Width; ++i){
for(int j = 1; j <= Width; ++j){
System.out.print(AdjMat[i][j] + " ");
}
System.out.println();
}
*/
for(int i = 1; i <= Width; ++i){
for(int j = 1; j <= Width; ++j){
if(AdjMat[i][j] == 1 && Visited[i][j] == 0){
DFS(i, j);
++idx;
}
if(cnt > 0){ // 어떤 영역의 DFS을 다 돌고 나면 초기화해준다.
result.add(cnt);
cnt = 0;
}
}
}
System.out.println(idx); // 단지의 개수
result.sort((x, y) -> x - y); // 오름차순
for(int r: result){
System.out.println(r); //면적의 개수 정렬
}
}
}- 결과 배열 처리하는 것 때문에 에러가 나고 복잡해져서(배열 사이즈 문제) 결괏값을 ArrayList에 저장하니까 해결됐다.
- 전에 작성했던 아래의 코드에서는 영역마다 배열에 영역 사이즈를 넣으려다가 오류가 났다.
-> 그런데, 모든 영역을 방문하기 전까지 resultArea[] 의 사이즈를 알 수 없기 때문에 문제가 생겼다.
-> 따라서, 배열에 비해서 사이즈에 유동적인 List를 활용하면 좋다.
- 지난 번에 풀 때 cnt 처리하는 부분에서 헤멨다. nextRow, nextCol을 찾은 경우에만 cnt++을 했더니 배열원소들이 내가 찾는 값보다 모두 1씩 작았다. (맨 처음 실행되는 DFS를 카운트하지 않아서 )
- 메서드 간에 실행 순서를 꼭 파악해야겠다.
참고) 프로그래머스의 컬러링북 색칠하기와 유사하다.
https://school.programmers.co.kr/learn/courses/30/lessons/1829
https://oranthy.tistory.com/261
========================오류 코드========================
코드업에서는 정답인데 백준에서는 채점 41% 쯤에 ArrayIndexOutOfBounds가 발생한다. 오류 수정이 필요한다.
<hide/>
import java.util.Arrays;
import java.util.Scanner;
public class HouseNumbering {
static int MAX_COUNT = 100;
static int[][] AdjMat = new int[MAX_COUNT][MAX_COUNT];
static int[][] Visited = new int[MAX_COUNT][MAX_COUNT];
static int Width = 0;
static int[][] DirMat = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
static int idx = 0;
static int[] resultArr = new int[MAX_COUNT];
public static void DFS(int _currRow, int _currCol){
Visited[_currRow][_currCol] = 1;
for(int i = 0; i < 4; ++i){
int nextRow = _currRow + DirMat[i][0];
int nextCol = _currCol + DirMat[i][1];
if(Visited[nextRow][nextCol] == 1 ||
nextRow <= 0 || nextRow > Width ||
nextCol <= 0 || nextCol > Width){
continue;
}
if(AdjMat[nextRow][nextCol] == 1){ // 같은 단지 내에서 DFS실행
++resultArr[idx];
System.out.printf("(%d, %d) -> (%d, %d)%n", _currRow, _currCol, nextRow, nextCol);
DFS(nextRow, nextCol);
}
}
}
public static void main(String[] args){
Scanner scan = new Scanner(System.in);
Width = scan.nextInt();
for(int i = 1; i <= Width; ++i){
String str = scan.next();
for(int j = 1; j <= Width; ++j){
AdjMat[i][j] = str.charAt(j - 1) - 48;
}
}
// 인접행렬 확인
// for(int i = 1; i <= Width; ++i){
// for(int j = 1; j <= Width; ++j){
// System.out.print(AdjMat[i][j] + " ");
// }
// System.out.println();
// }
for(int i = 1; i <= Width; ++i){
for(int j = 1; j <= Width; ++j){
if(AdjMat[i][j] == 1 && Visited[i][j] == 0){
DFS(i, j);
++idx;
}
}
}
System.out.println(idx);
for(int i = 0; i < idx; ++i){
resultArr[i] += 1;
}
int[] res = new int[idx]; // 2
for(int i = 0; i < idx; ++i){
res[i] = resultArr[i]; // 7 5
}
Arrays.sort(res); // 5 7
for(int r : res){
System.out.println(r);
}
}
}Note)
- 인접행렬의 값들이 붙어서 입력이 된다.
-> 따라서 String으로 입력 받는다.
-> str.charAt(j - 1) - 48;
- DFS 코드 안에서 새롭게 재귀함수가 돌아갈 때마다 resultArr[]의 값을 1씩 늘린다.
-> resultArr[0]의 값이 7일 때 재귀함수는 6번 실행이 된다.
-> 따라서, 마지막에 배열의 모든 값을 1씩 증가시켜줘야한다.
- index(영역의 개수)는 main함수에서 DFS가 끝날 때마다 증가시킨다.
<hide/>
[입력]
7
0110100
0110101
1110101
0000111
0100000
0111110
0111000
[출력]
3
7
8
9
[입력]
5
11100
01000
11010
01010
00111
[출력]
2
5
7
출처: https://codeup.kr/problem.php?id=4421
단지 번호 붙이기
문제1) <그림 1>과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집들의 모임인 단지를 정의하고, 단지에 번호를 붙이려
codeup.kr
https://www.acmicpc.net/problem/2667
2667번: 단지번호붙이기
<그림 1>과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여
www.acmicpc.net
'자료구조와 알고리듬 With Java > [Study] BAEKJOON 프로그래머스 CodeUp LeetCode' 카테고리의 다른 글
| DFS 촌수 찾기 (오류 수정 전) (0) | 2022.04.22 |
|---|---|
| 친구 찾기 (0) | 2022.04.22 |
| Code up 4024 호수의 수 구하기 (0) | 2022.04.21 |
| Java로 BFS 구현하기 (0) | 2022.04.20 |
| Code up 그림 개수 세기 (0) | 2022.04.20 |