[백준] 2667 단지번호붙이기 - BFS(넓이우선탐색) JAVA

https://www.acmicpc.net/problem/2667

2667번: 단지번호붙이기

문제풀이

BFS(넓이우선탐색) 를 활용합니다.

 

제가 놓쳤었어서 시간이 소요된점은

1. 시작시에 바로 visited[true]로 바뀌는 지점에 바로 지점의 갯수 (cnt + 1) 을 해주어야합니다.

2. Collections.sort() 는 기본적으로 오름차순 정렬이고, 여기에 Collections.reverseOrder()를 두번째 매개변수에 넣어주면 내림차순으로 변환됩니다.

Collections.sort(result, Collections.reverseOrder());

3. - 원래 Node 객체를 생성하여 BFS 과정을 수행하지만 이번에는 integer[]{x, y, cnt} 형태로 사용하여 진행해보았던 점이 특이사항입니다.

4. 첫번째 코드에는 결과값 result를 배열 25 * 25 에 넣어두고 하였는데 두번째 코드에서 list에 넣어두고 사용하여 불필요한 메모리공간을 사용하지않게 개선

 

 

문제에서 처음에 실수했던 부분은 PriorityQueue 부분입니다.

처음에는 PQ를 사용하므로 foreach 문으로 출력을 하더라도 알아서 정렬된 값이 나올 것이라 생각했습니다.

System.out.println(apartNum);
for(int v : ret){System.out.println(v);}

하지만 이 방식은 PriorityQueue의 내부 구조(힙)를 순회하기 때문에 정렬된 순서로 출력되지 않습니다.

 

그 대신에, 직접 모든 큐를 빼주면서 처리해야 올바르게 오름차순 구조로 나옵니다.

System.out.println(apartNum);
while(!ret.isEmpty()) {
    System.out.println(ret.poll());
}

코드

첫번쨰 코드.

import java.util.*;


public class Main {
	
	public static int N;
	public static int[][] map;
	public static boolean[][] visited;
	public static int[] result;
	public static int resultindex=0;
    public static void main(String[] args) {
    	Scanner sc = new Scanner(System.in);
    	N = sc.nextInt();
    	map = new int[N][N];
    	visited = new boolean[N][N];
    	result = new int[N*N];
    	for(int i=0;i<N;i++) {
    		String str = sc.next();
    		for(int j=0;j<N;j++) {
    			map[i][j] = str.charAt(j) - '0';
    		}
    	}
    	
    	for(int i=0;i<N;i++) {
    		for(int j=0;j<N;j++) {
    			if(map[i][j] == 1 && visited[i][j] == false) {
    				BFS(i,j);
    				resultindex+=1;
    			}
    		}
    	}
    	Arrays.sort(result);
    	System.out.println(resultindex);
    	for(int a : result) {
    		if(a == 0) continue;
    		System.out.println(a);
    	}
    		
    }
    
    public static void BFS(int startx, int starty) {
    	Queue<Integer[]> q = new LinkedList<>();
    	q.offer(new Integer[]{startx,starty, 0});
    	visited[startx][starty] = true;
    	int[] dx = {-1,1,0,0};
    	int[] dy = {0,0,-1,1};
    	result[resultindex] += 1;
    	
    	while(!q.isEmpty()) {
    		Integer[] temp = q.poll();
    		int x = temp[0];
    		int y = temp[1];
    		int cnt = temp[2];
        	for(int dir = 0; dir<4;dir++) {
        		int nx = x + dx[dir];
        		int ny = y + dy[dir];
        		if(nx < 0 || nx >= N || ny < 0 || ny >= N) continue;
        		if(map[nx][ny] == 0 || visited[nx][ny] == true) continue;
        		q.offer(new Integer[] {nx, ny, cnt+1});
        		visited[nx][ny] = true;
        		result[resultindex] += 1;  
        	}
    	}
    	
    }
    

}

 

 

두번째 코드

- 크게 달라진점은 없고 결과값 result를 이전에는 배열 25 * 25 에 넣어두고 하였는데 이제 list에 넣어두고 사용하여 불필요한 메모리공간을 사용하지 않습니다.

- 원래 Node 객체를 생성하여 BFS 과정을 수행하지만 이번에는 integer[]{x, y, cnt} 형태로 사용하여 진행해보았던 점이 특이사항입니다.

import java.util.*;


public class Main {
	
	public static int N;
	public static int[][] map;
	public static boolean[][] visited;
	public static ArrayList<Integer> result = new ArrayList<>();
	public static int resultindex=0;
	public static int count = 0;
    public static void main(String[] args) {
    	Scanner sc = new Scanner(System.in);
    	N = sc.nextInt();
    	map = new int[N][N];
    	visited = new boolean[N][N];
    	for(int i=0;i<N;i++) {
    		String str = sc.next();
    		for(int j=0;j<N;j++) {
    			map[i][j] = str.charAt(j) - '0';
    		}
    	}
    	
    	for(int i=0;i<N;i++) {
    		for(int j=0;j<N;j++) {
    			if(map[i][j] == 1 && visited[i][j] == false) {
    				count = 0;
    				BFS(i,j);
    				resultindex+=1;
    				result.add(count);
    			}
    		}
    	}
    	
    	Collections.sort(result);
    	System.out.println(resultindex);
    	
    	for(int a : result) {
    		if(a == 0) continue;
    		System.out.println(a);
    	}
    		
    }
    
    public static void BFS(int startx, int starty) {
    	Queue<Integer[]> q = new LinkedList<>();
    	q.offer(new Integer[]{startx,starty, 0});
    	visited[startx][starty] = true;
    	int[] dx = {-1,1,0,0};
    	int[] dy = {0,0,-1,1};
    	count += 1;
    	
    	
    	while(!q.isEmpty()) {
    		Integer[] temp = q.poll();
    		int x = temp[0];
    		int y = temp[1];
    		int cnt = temp[2];
        	for(int dir = 0; dir<4;dir++) {
        		int nx = x + dx[dir];
        		int ny = y + dy[dir];
        		if(nx < 0 || nx >= N || ny < 0 || ny >= N) continue;
        		if(map[nx][ny] == 0 || visited[nx][ny] == true) continue;
        		q.offer(new Integer[] {nx, ny, cnt+1});
        		visited[nx][ny] = true;
        		count += 1;  
        	}
    	}
    	
    }
    

}

 

정답코드3입니다.

package Main;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class Main {
	static int N, M, S, P, A, B, X, L, R, C, n, k, m, l, K, D, T, d, c;
	static int answer = 0;
	static int[][] matrix = new int[26][26];
	static boolean[][] visited = new boolean[26][26];
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken());
		for(int i=0;i<N;i++) {
			st = new StringTokenizer(br.readLine());
			String str = st.nextToken();
			for(int j=0; j<N; j++) {
				matrix[i][j] = str.charAt(j) == '0' ? 0 : 1;
			}
		}
		int apartNum = 0;
		PriorityQueue<Integer> ret = new PriorityQueue<>();
		for(int i=0;i<N;i++) {
			for(int j=0; j<N; j++) {
				if(matrix[i][j] == 1 && visited[i][j] == false) {
					ret.add(BFS(i, j, ++apartNum));
				}
			}
		}
		
		System.out.println(apartNum);
		while(!ret.isEmpty()) {
			System.out.println(ret.poll());
		}
	}
	
	static int BFS(int sr, int sc, int apartNum) {
		Queue<int[]> q = new LinkedList<>();
		q.offer(new int[] {sr, sc});
		matrix[sr][sc] = apartNum;
		visited[sr][sc] = true;
		int cnt = 1;
		while(!q.isEmpty()) {
			int[] temp = q.poll();
			for(int[] dir : new int[][] { {0,1}, {0, -1}, {-1, 0}, {1, 0} }) {
				int nr = temp[0] + dir[0];
				int nc = temp[1] + dir[1];
				
				if(nr < 0 || nr >= N || nc < 0 || nc >= N) continue;
				if(matrix[nr][nc] == 0) continue;
				if(visited[nr][nc] == true) continue;
				matrix[nr][nc] = apartNum;
				visited[nr][nc] = true;
				q.offer(new int[] { nr, nc});
				cnt += 1;
			}
		}
		return cnt;
	}
	
	
}