👌 단지번호붙이기
정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여기서 연결되었다는 것은 어떤 집이 좌우, 혹은 아래위로 다른 집이 있는 경우를 말한다. 대각선상에 집이 있는 경우는 연결된 것이 아니다. 지도를 입력하여 단지수를 출력하고, 각 단지에 속하는 집의 수를 오름차순으로 정렬하여 출력하는 프로그램을 작성하시오.
✔ 접근방법
기본적인 DFS를 사용하여 해결.
- 해당 그리드의 값이 1이고 (집이 존재하고) 아직 방문되지 않았다면, 단지수를 늘리고 해당 단지에 대해 dfs 실행 및 dfs 후 집수를 결과에 append
- 모든 그리드에 대하여 반복
DFS 알고리즘
- 방문으로 마크 및 집수++
- 상하좌우를 확인하고, 상하좌우의 값이 1이고 (집이 존재하고) 아직 방문되지 않았다면, dfs 재실행
✔ 코드
import java.util.Scanner;
import java.util.ArrayList;
public class p2667 {
//결과 배열, 방문 확인용 배열 및 변수 선언
static int[][] map = new int[26][26];
static boolean[][] visited = new boolean[26][26];
static int n = 0, complexCount = 0, houseCount = 0;
static int dx[] = {0, 0, 1, -1};
static int dy[] = {1, -1, 0, 0};
public static void main(String[] args){
//결과 arraylist 및 스캐너 선언
ArrayList<Integer> result = new ArrayList<Integer>();
Scanner scan = new Scanner(System.in);
n = scan.nextInt();
//인풋을 배열로 변환
for (int i = 0; i < n; i++) {
String temp = scan.next();
for (int j = 0; j < temp.length(); j++) {
//charAt을 하면 ASCII로 저장되므로 '0'을 빼준다 (48을 빼준다)
map[i][j] = temp.charAt(j) - '0';
}
}
//주 반복문
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
//만약 해당 포지션이 1이고 (집이 존재하고) 아직 방문되지 않았다면
if(map[i][j] == 1 && visited[i][j] == false){
//1.단지수를 늘리고
//2.집수를 0으로 초기화하고
//3.해당 단지에 대해 dfs 실행
//4.집수를 결과에 append
complexCount++;
houseCount = 0;
dfs(i,j);
result.add(houseCount);
}
}
}
//단지수 출력
System.out.println(complexCount);
//집 수를 오름차순으로 정렬 및 출력
result.sort(null);
for (int i = 0; i < result.size(); i++) {
System.out.println(result.get(i));
}
}
public static void dfs(int x, int y){
//방문됨으로 마크 및 집수++
visited[x][y] = true;
houseCount++;
//상하좌우에 대한 확인과정
for(int i = 0; i < 4; i++){
int ix = x + dx[i];
int iy = y + dy[i];
//상하좌우가 정해진 그리드 내에 존재하지 않을경우 continue
if(ix < 0 || ix >= n || iy < 0 || iy >= n){
continue;
}
//상하좌우가 1이고 (집이 존재하고) 아직 방문되지 않았으면 dfs 재실행
if(map[ix][iy] == 1 && visited[ix][iy] == false){
dfs(ix, iy);
}
}
}
}☝ 팁
dx,dy와for loop을 활용한 상하좌우 확인방법static int dx[] = {0, 0, 1, -1}; static int dy[] = {1, -1, 0, 0}; ... for(int i = 0; i < 4; i++){ int ix = x + dx[i]; int iy = y + dy[i];
String에서int로 변환시charAt을 사용하면 ASCII로 저장되는데, 이때'0'또는48을 빼주면 알맞은int로 저장map[i][j] = temp.charAt(j) - '0';
