[Java] 백준 1012번 (유기농 배추) [실버2]
https://www.acmicpc.net/problem/1012
이 문제로 그래프 탐색을 처음 접했는데 처음에는 어떻게 접근해야 할지 몰라서 풀지 못했다..
코딩 초보인 주제에 혼자서 풀어보겠다고 몇 시간씩 고민하며 생각했는데.. 1시간 정도 해보고 안되면 더 붙잡아선 안 될 것 같다.
요즘은 Chat-GPT가 있어서 막히는 문제가 생길때 문제 접근 방법을 물어볼 수 있어서 좋은 것 같다.
결국 다양한 유형의 문제를 많이 풀어보고 각 문제 유형별 정해진 접근법을 익히는게 중요한 것 같다.
물론 창의력과 사고력을 기르기 위해서는 혼자서 접근 방법을 찾아나가야 한다는 말도 맞지만, 그 말도 이미 유형별 기본적인 풀이 방법은 전부 알고 있는 플레티넘이나 다이아 이상이라는 전제에서나 맞는 말인 것 같다..
이 문제는 배추가 심어진 곳을 순차로 탐색하면서 각 탐색 지점으로부터 상하좌우 방향으로 확장해서 탐색하는 문제이다.
그리고 한 번 방문한 지점은 방문 표시를 해둬서 중복 방문을 하지 않도록 한다.
정답
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int T = Integer.parseInt(br.readLine());
for (int a = 0; a<T; a++) {
StringTokenizer st = new StringTokenizer(br.readLine());
int M = Integer.parseInt(st.nextToken());
int N = Integer.parseInt(st.nextToken());
int K = Integer.parseInt(st.nextToken());
int[][] filed = new int[M][N];
boolean[][] visited = new boolean[M][N];
List<int[]> cabbageList = new ArrayList<>();
for (int i=0; i<K; i++) {
st = new StringTokenizer(br.readLine());
int X = Integer.parseInt(st.nextToken());
int Y = Integer.parseInt(st.nextToken());
filed[X][Y] = 1; // 배추가 심어진 걸 표시
cabbageList.add(new int[]{X, Y}); // 배추 위치를 담은 리스트
}
int area = 0;
// 상하좌우 좌표
int[] dx = {0, 0, 1, -1};
int[] dy = {1, -1, 0, 0};
for (int[] p : cabbageList) {
int startX = p[0];
int startY = p[1];
if (visited[startX][startY] == false) { // 방문하지 않았으면 탐색 시작
area += 1;
Queue<int[]> queue = new LinkedList<>(); // 같은 영역의 배추 좌표를 담을 큐
queue.add(new int[] {startX, startY}); // 큐에 담고
visited[startX][startY] = true; // 방문 표시
while (queue.size() != 0) { // 큐에 좌표가 담겨 있을 때 실행
int[] pollArr = queue.poll();
int x = pollArr[0];
int y = pollArr[1];
for (int i=0; i<4; i++) { // 4회 반복
int nx = x + dx[i];
int ny = y + dy[i];
if (nx >= 0 && ny >= 0 && nx < M && ny < N) {
if (filed[nx][ny] == 1 && visited[nx][ny] == false) { // 배추가 있으면서 탐색 안했으면
queue.add(new int[] {nx, ny}); // 큐에 담기
visited[nx][ny] = true;
}
}
}
}
}
}
bw.write(area + "\n");
}
bw.flush();
bw.close();
}
}
풀이
1. 배추밭을 나타낼 filed, 방문 여부를 나타낼 visited, 배추의 위치만을 담을 cabbageList를 생성한다.
int[][] filed = new int[M][N]; // 배추밭
boolean[][] visited = new boolean[M][N]; // 방문 여부
List<int[]> cabbageList = new ArrayList<>(); // 배추 심어진 곳
2. 이후 K개의 배추 위치를 각각 filed 배열에 표시하고, cabbageList 리스트에 담는다.
for (int i=0; i<K; i++) {
st = new StringTokenizer(br.readLine());
int X = Integer.parseInt(st.nextToken());
int Y = Integer.parseInt(st.nextToken());
filed[X][Y] = 1; // 배추가 심어진 걸 표시
cabbageList.add(new int[]{X, Y}); // 배추 위치를 담은 리스트
}
이렇게 하면 filed에는 위와 같은 2차원 배열로 0과 1의 숫자가 담길거고, cabbageList에는 1의 좌표값만 담길 것이다.
3. 배추 영역의 개수를 표시할 area와 상하좌우 좌표를 나타낼 dx, dy를 선언한다.
int area = 0;
// 상하좌우 좌표
int[] dx = {0, 0, 1, -1};
int[] dy = {1, -1, 0, 0};
4. cabbageList에서 좌표값을 하나 뺐을 때, 그 좌표가 방문하지 않은 곳이라면, 그 좌표를 큐에 넣고 방문 표시를 한 뒤, 탐색을 시작한다.
for (int[] p : cabbageList) {
int startX = p[0];
int startY = p[1];
if (visited[startX][startY] == false) { // 방문하지 않았으면 탐색 시작
area += 1;
Queue<int[]> queue = new LinkedList<>(); // 같은 영역의 배추 좌표를 담을 큐
queue.add(new int[] {startX, startY}); // 큐에 담고
visited[startX][startY] = true; // 방문 표시
5. 탐색 시작 좌표를 중심으로 상하좌우를 탐색했을 때 배추가 존재하면서 방문하지 않은 곳이면 그 새로운 좌표를 큐에 넣고 방문 표시를 해준다.
만약 배추는 존재하는데 이미 방문한 곳이라면 큐에 넣지 않는다.
이렇게 해주는 이유는 이미 방문한 좌표는 재탐색을 할 필요가 없기 때문이다.
예를 들어 (0, 0)을 중심으로 상하좌우를 탐색했을 때 (0, 1)을 탐색했지만, 다음번에 (1, 1)을 중심으로 상하좌우를 탐색했을 때 다시 (0, 1)이 재탐색되기 때문에 시간 낭비가 된다.
또한, 새로운 탐색 좌표인 nx와 ny가 배추밭 영역을 넘어서지 않도록 if (nx >= 0 && ny >= 0 && nx < M && ny < N)를 통해 배추밭 영역 내의 좌표인지 확인해준다.
while (queue.size() != 0) { // 큐에 좌표가 담겨 있을 때 실행
int[] pollArr = queue.poll();
int x = pollArr[0];
int y = pollArr[1];
for (int i=0; i<4; i++) { // 4회 반복
int nx = x + dx[i];
int ny = y + dy[i];
if (nx >= 0 && ny >= 0 && nx < M && ny < N) {
if (filed[nx][ny] == 1 && visited[nx][ny] == false) { // 배추가 있으면서 탐색 안했으면
queue.add(new int[] {nx, ny}); // 큐에 담기
visited[nx][ny] = true;
}
}
}
}
}
}