[문제 풀이] 백준 2667번 단지번호붙이기 JAVA

문제

  문제접근 방법   

해당 문제는 가로와 세로의 크기가 같은 지도가 존재하고 1은 집이 존재하는 곳, 0은 집이 존재하지 않은 곳일 때, 지도를 통해 연결된 집의 모임인 단지를 정의하고 단지에 번호를 붙여야 한다. 지도의 크기는 N이고  N 줄에 N개의 수가 주어질 때 몇 개의 단지가 존재하는지와 각 단지 내 집의 수를 출력해야 한다.

 

처음 문제를 dfs나 bfs를 통해 탐색을 해야겠다는 생각이 들었고 범위가 크지 않아 두 방법 중 편한 방법을 선택해 풀이하면 좋을 것 같았다. 하지만 본인은 bfs가 조금 약하다고 생각해 bfs로 먼저 접근하였다.

알고 있듯이 bfs 너비 우선 탐색으로 Queue에 시작 인덱스와 인접 인덱스들을 모두 넣고 Queue가 빌 때까지 반복하는 방식으로 탐색하는 방법이다. 그래서 아래와 같이 bfs로 선언하고 현재 인덱스의 상하좌우를 비교하면서 1이면 Queue에 넣고 방문처리해 주는 방식으로 코드를 작성하였다.

< 최종 코드 >

import java.util.*;

public class Main{
    public static boolean visited[][];
    public static List<Integer> list=new LinkedList<>();
    public static void main(String args[]){
        Scanner s=new Scanner(System.in);
        
        int n=s.nextInt();
        int map[][]=new int[n+1][n+1];
        visited=new boolean[n+1][n+1];
        for(int i=1;i<=n;i++){
            String str=s.next();
            for(int j=1;j<=n;j++){
                map[i][j]=str.charAt(j-1)-'0';
            } 
        }
        
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                if(!visited[i][j]&&map[i][j]==1){
                    bfs(i,j,map);
                }
            }
        }
        StringBuilder sb=new StringBuilder();
        sb.append(list.size()).append("\n");
        Collections.sort(list);
        for(int i=0;i<list.size();i++){
            sb.append(list.get(i)).append("\n");
        }
        System.out.print(sb);
    }
    public static void bfs(int i,int j,int map[][]){
        Queue<int[]> queue=new LinkedList<>();
        queue.offer(new int[]{i,j});
        visited[i][j]=true;
        int cnt=1;
        int x[]={0,0,-1,1};//상하좌우
        int y[]={-1,1,0,0};
        while(!queue.isEmpty()){
            int xy[]=queue.poll();
           
            for(int k=0;k<4;k++){
                int nx=xy[1]+x[k];
                int ny=xy[0]+y[k];
                if(ny<map[0].length&&ny>0&&nx<map[0].length&&nx>0){
                    if(!visited[ny][nx]&&map[ny][nx]==1){
                        queue.offer(new int[]{ny,nx});
                        visited[ny][nx]=true;
                        cnt++; 
                    }
                    
                }
            }
            
        }
        list.add(cnt);
    }
}

먼저 처음에는 해당 코드처럼 작성하지 못했다 거의 다 작성했지만 코드를 돌려보니 몇 가지 문제가 존재하였다.

• 첫 번째 문제 map에 1을 입력한 자리에 48이 저장되어 있었고 해당 문제는 map을 입력받을 때 String형을 charAt()를 통해 char형으로 저장했는데 이때 map은 int형이라 형변한을 해줘야 한다. 그래서 처음에는 map [i][j]=(int) str.charAt(j-1);처럼 형변환을 시도해 봤지만 (int) 형변환 시 유니코드 값(아스키코드)이 그대로 반환되어 아래에서 조건문들이 제대로 작동하지 못한다는 것을 확인하여 map [i][j]=str.charAt(j-1)-'0';처럼 코드를 수정하였다.
• 두 번째 문제는 답은 제대로 나오는데 틀렸다는 판정을 받아 문제를 자세히 읽어보던 중 오름차순이라는 것을 간과하고 문제를 해결해 sort를 추가 작성하는 것으로 문제를 해결하였다.

이후 코드 흐름은 위에서 간단하게 언급하였듯이  map [][]의 값이 1이고 방문한 적이 없는 인덱스가 Queue에 처음 들어가게 되고 반복문에서 Queue가 비어 있을 때까지 반복하는데 반복 내용은 다음과 같다.

• 큐에 넣어있던 인덱스를 poll 한다.
• map [][]의 값이 1이고 방문한 적이 없는 인덱스를 Queue에 offer 한다.
• visited [][]를 방문처리한다.
• cnt값을 증가시켜준다.

 Queue가 비어있을 때까지 반복하고 반복이 끝나면 list에 cnt의 값을 저장하는 방식이다.

 여기서 인접한 변을 탐색하는 방식은 x, y 배열에 상하좌우 값을 미리 넣어 두고 반복문을 통해 상하좌우 인접하는 변 중 1이 존재하는지를 반복하는 방식으로 탐색한다.  map값이 1이면 Queue에 넣고  다시 반복할 때 int xy []=queue.poll();로 시간 인덱스를 갱신해 주고 갱신된 인덱스의 상하좌우 이런 식으로 반복해서 Queue에 넣어 탐색해

최종적으로 연결된 단지의 크기와 단지의 개수를 측정하는 방식이다.

 

  마무리  

해당 문제는 기초적인 dfs, bfs 문제가 아닌 약간의 변형과 생각을 하게 하는 문제였다. 상하좌우를 어떤 식으로 접근해야 할지와 dfs를 사용해서 탐색할지 bfs를 활용할지 완전탐색을 진행해야 할지 등 여러 가지를 고려해야 해 재미있게 풀이했던 문제이다.

또 기초적인 형태를 넘어 응용을 통해 탐색하는 방식으로 기초적인 응용문제로 생각된 꼭 풀어볼 것을 추천한다.

  추가 코드 분석 및 풀이  

해당 문제는 BFS로 풀이하던지 DFS로 풀이한 던 지 성능의 차이는 존재할 수 있지만 문제 해결에 있어서 큰 문제는 없다.

그래서 처음에는 익숙하지 않은 BFS로 문제를 풀이했었고 아래에서는 DFS로도 접근해서 문제를 해결해 보도록 하겠다.

 

< 추가 풀이 ver DFS >

- 추후 업데이트 예정