오늘의 학습내용
- DFS
- 문자를 숫자로 변환하는 법
공부한 내용
처음 문자열을 받고 숫자배열로 넣고자 할때 다음과 같은 방식으로 시도했었다.
for(int i=0; i<N; i++){
char[] input = br.readLine().toCharArray();
for(int j=0; j<N; j++){
map[i][j] = input[j] + '0';
}
}물론 char 와 int 의 연산은 int 로 계산되는 연산자간의 우선순위가 존재하지만 위의 방식은 ìnput[j]값에 '0'의 ASCII 값을 더하기 때문에 원하는 값보다 훨씬 큰 값을 가지게된다.
따라서 input[j] 자신의 값을 저장하게끔 하려면 map[i][j] = input[j] + '0' 대신 map[i][j] = input[j] - '0' 로 해야 정확한 배열이 저장된다.
오늘의 회고
처음 시도에서는 완전탐색을 이용하여 구하려고 했다.
1) 입력받는 수들을 map 이라는 2차원 배열에 저장해두고 (0,0) 부터 탐색을 시작한다.
2) 방문했는지 여부를 확인하면서 (x-1, y) (x, y-1) 의 좌표가 1인지-동일한 단지 내에 있는 좌표인지 확인하기 위해-를 고려한다.
3) 만약 방문하지 않은 좌표가 0 이면서 주변에 이어지는 1이 있는지를 확인한다.
4) 이를 반복하면서 ArrayList에 cnt값을 넣고 정렬한다.
위 방법으로 시도해봤는데 탐색을 하다가 원위치로 되돌아가는 방법이 쉽지가 않았다. (이는 즉, 탐색을 진행하다가 고립된 순간이 오면 원위치로 돌아가서 cnt를 초기화시키고 다시 탐색을 해야하는데 이중 for문으로 진행하면 돌아가는 방법이 복잡하다는 의미이다.) 따라서 재귀적으로 구현해야겠다는 생각이 들었고 그 방법으로 고안해낸 코드가 dfs를 이용한 다음의 코드이다.
문제
<그림 1>과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여기서 연결되었다는 것은 어떤 집이 좌우, 혹은 아래위로 다른 집이 있는 경우를 말한다. 대각선상에 집이 있는 경우는 연결된 것이 아니다. <그림 2>는 <그림 1>을 단지별로 번호를 붙인 것이다. 지도를 입력하여 단지수를 출력하고, 각 단지에 속하는 집의 수를 오름차순으로 정렬하여 출력하는 프로그램을 작성하시오.
내 풀이
package baekjoon.dfs;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
public class 단지번호붙이기 {
private static int[][] map;
private static boolean[][] visited;
private static int N, cnt;
private static ArrayList<Integer> ans;
private static int[] dx = {0, 1, 0, -1};
private static int[] dy = {1, 0, -1, 0};
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
map = new int[N][N];
visited = new boolean[N][N];
for(int i=0; i<N; i++){
String input = br.readLine();
for(int j=0; j<N; j++){
map[i][j] = input.charAt(j) - '0';
}
}
ans = new ArrayList<>();
cnt = 1;
for(int i=0; i<N; i++){
for(int j=0; j<N; j++){
if(!visited[i][j] && map[i][j] == 1){
dfs(i, j);
ans.add(cnt);
cnt = 1;
}
}
}
Collections.sort(ans);
System.out.println(ans.size());
for(int i=0; i<ans.size(); i++){
System.out.println(ans.get(i));
}
}
public static void dfs(int x, int y){
visited[x][y] = true;
for(int i=0; i<4; i++){
int nx = x + dx[i];
int ny = y + dy[i];
if(nx >= 0 && ny >= 0 && nx <N && ny <N){
if(!visited[nx][ny] && map[nx][ny]==1){
cnt++;
dfs(nx, ny);
}
}
}
}
}
