[백준/java] 2667번 :단지번호붙이기 - BFS

2667번 :단지번호붙이기

 

728x90

 

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

2667번: 단지번호붙이기

 

2667번 :단지번호붙이기

 

※ 문제풀이

이번 문제는  그림(1926)문제와 방법은 똑같고 다만 BFS 탐색할 때 해당 위치가 중복되는지 한번 더 확인해주면 된다.

 

탐색하는 위치의 방문 여부를 한번 더 해주지 않으면 단지의 개수가 불필요하게 더 늘어나게 된다.

 

 

반응형

 

문제가 됐던 부분은 아래와 같다.

List<Integer> complex = new ArrayList<Integer>();
		
for (int i = 0; i < N; i++) {
	for (int j = 0; j < N; j++) {
		if(map[i][j] != 1 || visit[i][j]) continue;
				
		Queue<Node> q = new LinkedList<Node>();
		q.add(new Node(i, j));
		cnt = 0;
			
		while(!q.isEmpty()) {
			Node cur = q.poll();
				
			// 중복으로 체크하는 부분이 있는지 다시한번 확인해준다.
			if(visit[cur.y][cur.x]) continue;
					
			cnt++;
			visit[cur.y][cur.x] = true;
					
			for (int dir = 0; dir < 4; dir++) {						
				int ny = cur.y + dy[dir];
				int nx = cur.x + dx[dir];
						
				if(ny < 0 || ny >= N || nx < 0 || nx >= N) continue;
				if(visit[ny][nx] || map[ny][nx] != 1) continue;
						
				q.add(new Node(ny, nx));
			}
		}
				
		complex.add(cnt);
	}
}

 

여기서 

// 중복으로 체크하는 부분이 있는지 다시한번 확인해준다.
if(visit[cur.y][cur.x]) continue;

이 소스가 빠지게 되면 원래 나와야될 값보다 더 큰 값들을 볼 수있다.

 

전체 소스는 아래와 같다.

package bfs;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class ComplexNumbering {
	static int[] dy = {1, 0, -1, 0};
	static int[] dx = {0, 1, 0, -1};
	static boolean[][] visit;
	static int[][] map;
	static int N, cnt;
	static class Node {
		int y, x;
		public Node(int y, int x) {
			this.y = y;
			this.x = x;
		}
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		N = stoi(br.readLine());
		map = new int[N][N];
		visit = new boolean[N][N];
		
		for (int i = 0; i < N; i++) {
			String[] arr = br.readLine().split("");
			for (int j = 0; j < N; j++) {
				map[i][j] = stoi(arr[j]);
			}
		}
		
		List<Integer> complex = new ArrayList<Integer>();
		
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				if(map[i][j] != 1 || visit[i][j]) continue;
				
				Queue<Node> q = new LinkedList<Node>();
				q.add(new Node(i, j));
				cnt = 0;
				
				while(!q.isEmpty()) {
					Node cur = q.poll();
					
					// 중복으로 체크하는 부분이 있는지 다시한번 확인해준다.
					if(visit[cur.y][cur.x]) continue;
					
					cnt++;
					visit[cur.y][cur.x] = true;
					
					for (int dir = 0; dir < 4; dir++) {
						
						int ny = cur.y + dy[dir];
						int nx = cur.x + dx[dir];
						
						if(ny < 0 || ny >= N || nx < 0 || nx >= N) continue;
						if(visit[ny][nx] || map[ny][nx] != 1) continue;
						
						q.add(new Node(ny, nx));
					}
				}
				
				complex.add(cnt);
			}
		}
		
		bw.write(complex.size() + "\n");
		
		// 정렬 후 출력
		Collections.sort(complex);
		for (int i = 0; i < complex.size(); i++) {
			bw.write(complex.get(i) + "\n");
		}
		
		bw.flush();
	}
	
	public static int stoi(String str) {
		return Integer.parseInt(str);
	}
}