문제

BOJ 16932: 모양 만들기 https://www.acmicpc.net/problem/16932

풀이

1. map에 값을 입력받을 때 0좌표를 zeroQ 큐에 넣는다.(이유는 아래 코드의 주석에 있음)

2. map을 돌며 1을 만날 때 마다 bfs를 시작한다.

   • 탐색된 1의 덩어리마다 index 값으로 모두 바꿔준다.
   • 해당 덩어리의 크기를 list에 넣어준다.
     • 여기서 list의 0번째 인덱스에 0을 넣어준다.(이유는 아래 코드의 주석에 있음)

1 1 0 0　　　　　　　　　　1 1 0 0
1 0 1 0　　　　　　　　　　1 0 2 0
1 0 1 0　　　　　　　　　　1 0 2 0　　　이런 식으로 덩어리 값들을 인덱스 값으로 바꿔준다
0 1 1 0　　　　　　　　　　0 2 2 0
1 0 0 1　　　　　　　　　　3 0 0 4　　　　　　　　　　

3. zeroQ에서 큐가 모두 빌 때 까지 뽑아내며 해당 0의 좌표에서 동서남북으로 탐색을 시작한다.
   • mergeBfs를 통해 0 기준으로 동서남북을 탐색한다.
   • 탐색한 좌표에 있는 덩어리의 index를 set에 넣는다.(중복값을 제거하기 위해)
   • set 에서 뺀 값을 list의 인덱스로 하여 덩어리들의 크기를 모두 더한 뒤 반환한다.

코드

import java.util.*;
import java.io.*;

public class Main {
	
	static int N, M;
	static int[][] map; // 원본 배열
	static boolean[][] isVisited; // bfs할 때 방문 처리 해줄 배열
	static int[] dx = {0, -1, 0, 1};
	static int[] dy = {-1, 0, 1, 0};
	static int index; // 덩어리 별로 매겨 줄 인덱스
	static ArrayList<Integer> list; // 각 덩어리(인덱스) 크기

	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());
		M = Integer.parseInt(st.nextToken());
		
		
		Queue<Pos> zeroQ = new LinkedList<>(); // 배열 중 0인 부분의 동서남북을 탐색할 거라서 그 0의 위치를 넣을 큐
		isVisited = new boolean[N][M];
		map = new int[N][M];

		for(int i=0; i<N; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			for(int j=0; j<M; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
				if(map[i][j] == 0) { // 배열 중 0인 값은 큐에 넣는다
					zeroQ.add(new Pos(i, j));
				}
			}
		}
		
		list = new ArrayList<>();
		list.add(0); // 각 덩어리의 인덱스가 1부터 시작할 것이기 때문에 && 덩어리 합칠 때 좌표가 0인 값은 덩어리 크기가 0이라서 0으로 해줌
		int maxSize = 0; // 답이 될 덩어리의 최댓값
		int newSize = 0; // 합치기 전의 덩어리들 크기
		int mergeSize = 0; // 합치고 나서의 덩어리 크기
		index = 1; // 덩어리의 인덱스는 1번부터 시작
		int[][] nMap = copyMap(); // 새로운 배열을 생성해서 해결함
		
		for(int i=0; i<N; i++) {
			for(int j=0; j<M; j++) {
				if(map[i][j] == 1 && !isVisited[i][j]) { // 원본 배열에서 값이 1이고 아직 방문하지 않았다면
					newSize = bfs(i, j, nMap, index); // bfs를 통해 덩어리의 크기를 구하고 그 덩어리들의 값을 인덱스 값으로 바꿔줌
					index++; // 다음 덩어리의 인덱스 값
					list.add(newSize); // 현재 덩어리(인덱스)의 덩어리 크기를 리스트에 넣어줌
				}
			}
		}
		
		while(!zeroQ.isEmpty()) { // 0이 들어간 큐를 탐색하며 0 기준 동서남북을 탐색하며 덩어리들을 합친다
			Pos p = zeroQ.poll();
			
			int curX = p.x;
			int curY = p.y;
			
			mergeSize = mergeBfs(curX, curY, nMap); // 덩어리를 합침
			
			maxSize = Math.max(maxSize, mergeSize); // 합친 덩어리 중 최댓값 구하기
		}
		
		System.out.println(maxSize);
	}
	
	// BFS를 통해 덩어리의 크기를 구해 반환하고 해당 덩어리를 인덱스 값으로 바꿔주는 메소드
	static int bfs(int x, int y, int[][] nMap, int index) {
		Queue<Pos> que = new LinkedList<>();
		
		int size = 1; // 덩어리의 사이즈 초깃값
		que.add(new Pos(x, y));
		isVisited[x][y] = true;
		nMap[x][y] = index; // 현재 덩어리의 값을 인덱스 값으로 바꿔줌
		
		while(!que.isEmpty()) {
			Pos p = que.poll();
			
			int curX = p.x;
			int curY = p.y;
			
			for(int t=0; t<4; t++) {
				int nx = curX + dx[t];
				int ny = curY + dy[t];
				
				if(nx < 0 || ny < 0 || nx >= N || ny >= M) continue;
				
				if(!isVisited[nx][ny] && nMap[nx][ny] == 1) {
					que.add(new Pos(nx, ny));
					isVisited[nx][ny] = true;
					nMap[nx][ny] = index; // 현재 덩어리의 값을 인덱스 값으로 바꿔줌
					size++;	// 현재 덩어리의 크기를 구함
				}
			}
			
		}
		
		return size; // 현재 덩어리의 크기를 반환
	}
	
	// 0 기준으로 동서남북을 탐색하며 덩어리들을 합쳐서 합친 크기를 반환하는 메소드
	static int mergeBfs(int x, int y, int[][] nMap) {
		HashSet<Integer> set = new HashSet<>(); // HashSet을 통해 0 기준 동서남북에 있는 덩어리들의 인덱스를 중복 없이 넣음
		int mergeSize = 0;
		
		for(int t=0; t<4; t++) {
			int nx = x + dx[t];
			int ny = y + dy[t];
			
			if(nx < 0 || ny < 0 || nx >= N || ny >= M) continue;
			
			set.add(nMap[nx][ny]); // 덩어리들의 인덱스를 중복 없이 넣음
		}
		
		for(int idx : set) { // set에 있는 인덱스들(덩어리 종류)를 모두 꺼내며 해당 덩어리의 크기를 모두 합침
			mergeSize += list.get(idx);
		}
		
		return mergeSize + 1; // 덩어리의 크기를 합치고 기준이 되었던 0도 크기 1을 가지기 때문에 1을 더해줌
	}
	
	// 배열 복사
	static int[][] copyMap() {
		int[][] nMap = new int[N][M];
		for(int i=0; i<N; i++) {
			for(int j=0; j<M; j++) {
				nMap[i][j] = map[i][j];
			}
		}
		
		return nMap;
	}
	
	static class Pos{
		int x, y;
		
		Pos(int x, int y){
			this.x = x;
			this.y = y;
		}
		
	}
	
}

정리

• map 배열의 0 자리에 1을 넣어가며 브루트포스식으로 했더니 시간초과가 나왔다.
• 덩어리들의 중복을 제거하기 위해 HashSet을 사용하였다.
• 덩어리 별로 구분하기 위해 해당 덩어리의 값을 index로 바꿔준다.