[BOJ][JAVA] 1012번: 유기농 배추

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

1012번: 유기농 배추

import java.util.*;

class Main {
	// https://www.acmicpc.net/problem/1012

	static int[] dx = { -1, 0, 1, 0 };
	static int[] dy = { 0, 1, 0, -1 }; // 사방 돌기
	static boolean[][] v;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int tc = sc.nextInt();
		StringBuilder sb = new StringBuilder();
		for (int t = 0; t < tc; t++) {
			int m = sc.nextInt();
			int n = sc.nextInt();
			int baechu = sc.nextInt();
			int[][] map = new int[m][n];
			v = new boolean[m][n];
			for (int i = 0; i < baechu; i++) {
				int x = sc.nextInt();
				int y = sc.nextInt();
				map[x][y] = 1;
			}
			// 여기까지 맵 짜는 거
			int sum = 0;
			// bfs 짜기
			for (int x = 0; x < m; x++) {
				for (int y = 0; y < n; y++) {
					if (map[x][y] == 1 && !v[x][y]) {
						sum++;
						Queue<Integer> q = new LinkedList<>();
						q.offer(map[x][y]);
						v[x][y] = true;
						while (!q.isEmpty()) {
							q.poll();
							for (int i = 0; i < 4; i++) {
								int nx = dx[i] + x;
								int ny = dy[i] + y;
								if (!v[nx][ny] && nx < m && nx >= 0 && ny < n && ny >= 0) {
									q.offer(map[nx][ny]);
									v[nx][ny] = true;
								}
							}
						}
					}
				}
			}
			sb.append(sum).append("\n");
		}
		System.out.println(sb);

		sc.close();
	}
}

 

 

---

오답노트(푸는 동안 사고과정 및 개선점)

접근은 맞았으나 BFS 돌릴 때가 잘못됐다. 좌표를 받아서 그걸 기점으로 bfs를 돌려야 되는데 이렇게하면 원하는 대로 돌지 않는다.

확실하게 구역이 나눠진 개수를 세는 것이라서 전형적인 bfs, dfs 문제다. 아마 dfs로 풀었으면 한번에 풀렸을 것이다.

---

정답코드

import java.util.*;

class Main {
	// https://www.acmicpc.net/problem/1012

	static int[] dx = { -1, 0, 1, 0 };
	static int[] dy = { 0, 1, 0, -1 }; // 사방 돌기
	static int n;
	static int m;
	static int[][] map;
	static boolean[][] v;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int tc = sc.nextInt();
		StringBuilder sb = new StringBuilder();
		for (int t = 0; t < tc; t++) {
			m = sc.nextInt();
			n = sc.nextInt();
			int baechu = sc.nextInt();
			// nxm 이 자연스럽다.
			map = new int[n][m];
			v = new boolean[n][m];

			int sum = 0;

			for (int i = 0; i < baechu; i++) {
				int c = sc.nextInt();
				int r = sc.nextInt();
				map[r][c] = 1;
			}

			for (int i = 0; i < n; i++) {
				for (int j = 0; j < m; j++) {
					if (!v[i][j] && map[i][j] == 1) {
						sum++;
						bfs(i, j);
					}
				}
			}
			sb.append(sum).append("\n");
		}
		System.out.println(sb);

		sc.close();
	}

	public static void bfs(int x, int y) {
		Queue<int[]> q = new LinkedList<>();
		q.offer(new int[] { x, y });
		v[x][y] = true;

		while (!q.isEmpty()) {
			int[] curr = q.poll();
			int cx = curr[0];
			int cy = curr[1];

			for (int k = 0; k < 4; k++) {
				int nx = cx + dx[k];
				int ny = cy + dy[k];
				if (nx >= 0 && nx < n && ny >= 0 && ny < m && !v[nx][ny] && map[nx][ny] == 1) {
					q.offer(new int[] { nx, ny });
					v[nx][ny] = true;
				}
			}
		}
	}
}

 

전체 정답 코드다. bfs만 똑 떼가지고 천천히 보자.

public static void bfs(int x, int y) {
		Queue<int[]> q = new LinkedList<>();
		q.offer(new int[] { x, y });
		v[x][y] = true;

		while (!q.isEmpty()) {
			int[] curr = q.poll();
			int cx = curr[0];
			int cy = curr[1];

			for (int k = 0; k < 4; k++) {
				int nx = cx + dx[k];
				int ny = cy + dy[k];
				if (nx >= 0 && nx < n && ny >= 0 && ny < m && !v[nx][ny] && map[nx][ny] == 1) {
					q.offer(new int[] { nx, ny });
					v[nx][ny] = true;
				}
			}
		}
	}

Queue의 Typed으로 int배열을 넣고, 큐 시작할 때 현재 위치(1이 검출된) 좌표를 크기 2짜리 초기화된 int배열로 넣어준다.
이게 C++이나 코틀린이었다면 pair를 사용했으면 될 테지만 자바는 그런게 없다. 클래스 만들어서 쓰는 방법은 아직 익숙하지않아서 크기 2짜리 배열로 대신했다.

 

이 배열로 좌표를 받는 것을 제외하면 원래 짠 코드에서 다를게 없다.

도움이 됐다면 댓글이나 공감 버튼 한 번씩 누르고 가주세요! 로그인 안해도 됩니다 ^_^