[Baekjoon] 14145_Žetva

문제(출처: https://www.acmicpc.net/problem/14145)

---

< Žetva >

 

문제 풀이 

 

bfs 알고리즘을 활용하여 먼저 영역 크기를 구한다. 영역 크기가 작은 곳부터 bfs 알고리즘을 활용하여 영역을 채운다.

 

 my solution (Java)

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Comparator;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.StringTokenizer;

public class _14145_ { // Žetva
	static int arr[][], result[][];
	static boolean visited[][];
	static int dx[] = { -1, 1, 0, 0 };
	static int dy[] = { 0, 0, -1, 1 };
    
	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st = new StringTokenizer(bf.readLine());
        
		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());
        
		arr = new int[n][m];
		for (int i = 0; i < n; i++) {
			String str = bf.readLine();
			for (int j = 0; j < m; j++) {
				arr[i][j] = str.charAt(j) - '0';
			}
		}
        
		visited = new boolean[n][m];
		PriorityQueue<int[]> queue = new PriorityQueue<>(new Comparator<int[]>() {
			@Override
			public int compare(int[] o1, int[] o2) {
				return o1[0] - o2[0];
			}
		});
        
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				if (arr[i][j] == 1 && !visited[i][j]) {
					visited[i][j] = true;
					queue.add(new int[] { findArea(i, j), i, j });
				}
			}
		}
        
		result = new int[n][m];
		int idx = 1;
		while (!queue.isEmpty()) {
			int temp[] = queue.poll();
			bfs(temp[1], temp[2], idx++);
		}
        
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				bw.write(result[i][j] + "");
			}
			bw.write("\n");
		}
		bw.flush();
	}
	private static void bfs(int i, int j, int idx) {
		Queue<int[]> queue = new LinkedList<>();
		queue.add(new int[] { i, j });
        
		visited[i][j] = false;
		result[i][j] = idx;
        
		while (!queue.isEmpty()) {
			int temp[] = queue.poll();
			for (int k = 0; k < 4; k++) {
				int x = temp[0] + dx[k];
				int y = temp[1] + dy[k];
				if (x >= 0 && x < visited.length && y >= 0 && y < visited[0].length && visited[x][y]
						&& arr[x][y] == 1) {
					visited[x][y] = false;
					result[x][y] = idx;
					queue.add(new int[] { x, y });
				}
			}
		}
	}
    
	private static int findArea(int i, int j) {
		Queue<int[]> queue = new LinkedList<>();
		queue.add(new int[] { i, j });
		int cnt = 1;
        
		while (!queue.isEmpty()) {
			int temp[] = queue.poll();
			for (int k = 0; k < 4; k++) {
				int x = temp[0] + dx[k];
				int y = temp[1] + dy[k];
				if (x >= 0 && x < visited.length && y >= 0 && y < visited[0].length && !visited[x][y]
						&& arr[x][y] == 1) {
					visited[x][y] = true;
					cnt += 1;
					queue.add(new int[] { x, y });
				}
			}
		}
		return cnt;
	}
}

변수)
n, m : 배열 크기
arr : 배열 정보
visited : 방문 여부
queue : 우선순위 큐 
result : 결과 배열
dx, dy : 이동 방향

 

배열 크기를 입력받아 배열 크기만큼 정보를 입력받는다. 배열 값이 1이고 아직 방문하지 않았다면 방문 표시와 queue에 findArea함수 반환값과 위치를 저장한다. queue가 빌 때까지 poll 하며 bfs 함수를 호출해 result 배열을 채운다. 최종 result 배열을 출력한다.

 

bfs(int i, int j, int idx)

Queue에 시작 위치를 저장한다. 시작 위치를 방문처리하며 result에 idx를 저장한다. Queue가 빌 때까지 다음 과정을 반복한다.

1) Queue poll

2) 4방향으로 탐색 후 배열 범위 안이며 아직 방문하지 않은 곳이고 arr 값이 1이라면 방문 표시 및 result에 idx 저장, Queue에 추가

 

findArea(int i, int j)

Queue에 시작 위치를 저장한다. Queue가 빌 때까지 다음 과정을 반복한다.

1) Queue poll

2) 4방향으로 탐색 후 배열 범위 안이며 아직 방문하지 않은 곳이고 arr 값이 1이라면 방문 표시 및 cnt+1, Queue에 추가

cnt를 반환한다.

 

---

---