[JAVA] 1012번 유기농 배추
문제 탐색하기
- 문제에서 구해야 하는 최종 정답은 무엇인지 탐색한 과정
- 그 정답을 구하기 위해 어떻게 코드를 구현해야 할지 고민한 과정
- 문제에 들어오는 범위를 파악하여 어떤 알고리즘을 쓸 수 있을지 고민해 가는 과정
각 해당칸의 상하좌우에 인접한(1)게 있으면 하나로 묶으면 된다.
인접한걸 하나로 보는거 -> DFS/BFS
이 문제는 이차원 배열이 주어지는데 고민이 됐던건 인접리스트로 접근할지, 인접행렬로 접근할지였다.
왜냐면 인접리스트의 시간복잡도는 O(V+E)이지만 인접행렬의 시간복잡도는 O(V^2)이기 때문이다.
이 문제에서 시간복잡도를 먼저 구해보자
V (정점 수) = 배추의 개수 = K (최악의 경우 M*N개)
E (간선 수) = 4*K (최대 4개의 인접한 위치가 있을 수 있으니까)
인접리스트: O(V + E) = O(2500 + 10,000) = O(12.500)
인접행렬: O(V^2) = O(2500^2) = O(6,250,000)
둘다 1초안에 충분히 가능하다.
그래서 배추의 위치가 이차원배열로 주어지니까 인접행렬로 접근했다
그리고 이 문제에서는 해당 칸과 인접한 곳에 1이 있는지(배추가 있는지) 확인해야한다.
그래서 상하좌우를 살펴봐야한다!
일반화를 시켜보면 다음 그림과 같다 그래서 미리 배열에 만들어두면 된다!
각 상하좌우가 기존의 x,y에서 얼만큼 이동했는지를 미리 저장한 배열이다
static int[] dx = {0,0,-1,1};
static int[] dy = {-1,1,0,0};이렇게 하면 나중에 x에서 dx만큼 더하면 이동한 곳의 좌표가 된다!
그리고 테스트 갯수가 주어지니까
t만큼 돌면서 그 안에서 n,m,k를 입력받고, 방문배열, 인접행렬을 생성하고, n*m만큼 또 반복문 돌면서 dfs를 체크해야한다.
코드 설계하기
위의 문제 탐색하기에서 고민한 과정을 토대로 문제 풀이에 대한 실마리를 잡았다면, 문제 풀이를 본격적으로 하기전, 문제를 풀이 위한 로드맵을 그려본다
어떤 순서로 코드를 작성해야 할지, 어떤 함수들을 작성해야 할지 등을 작성
1. t만큼 입력을 받으면서
2. t반복문안에서 n,m,k입력받고 배추 입력받고 dfs수행한다
3. 출력
시도 회차 수정 사항
- 무분별하게 "맞았습니다" 가 나올때까지 수정하는 형태의 문제 풀이를 반복하면, 내가 어떤 실수를 해서 해당 문제를 틀렸는지 모르게 된다
- 틀렸습니다를 받았다면 왜 틀렸는지 고민핸보고, 어떻게 수정할 수 있는지 고민하는 과정을 작성
- 위에 내가 세울 설계에서 어떤 부분이 틀렸는지도 함께 점검
틀린부분
1. 가로,세로가 너무 헷갈려서 이거때문에 adjMatrix[x][y] = 1; 여기 x,y를 반대로 적어서 인덱스길이초과 에러가 발생했다
배추 k를 입력받을때 이렇게 입력을 받는데 9가 열이고 6이 행이다! 그래서 처음에 헷갈렸고 계속 헷갈려서 에러가 났다
7 5
8 5
9 5
7 6
2. 배추 입력받기랑, dfs수행하는걸 t반복문 밖에서 수행했다
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main {
static int[][] adjMatrix;
static int n,m,k=0;
static boolean[][] isVisited;
static int[] dx = {0,0,-1,1};
static int[] dy = {-1,1,0,0};
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int t = Integer.parseInt(br.readLine());
StringTokenizer st;
StringBuilder sb = new StringBuilder();
for(int i=0; i<t; i++) {
st = new StringTokenizer(br.readLine(), " ");
n = Integer.parseInt(st.nextToken());
m = Integer.parseInt(st.nextToken());
k = Integer.parseInt(st.nextToken());
isVisited = new boolean[n][m];
adjMatrix = new int[n][m];
// 배추 입력받기
for(int j=0; j<k; j++) {
st = new StringTokenizer(br.readLine());
int x = Integer.parseInt(st.nextToken());
int y = Integer.parseInt(st.nextToken());
adjMatrix[x][y] = 1;
}
int cnt = 0;
for(int k=0; k<n; k++) {
for(int j=0; j<m; j++) {
if(adjMatrix[k][j] == 1 && !isVisited[k][j]) {
dfs(k,j);
cnt++;
}
}
}
sb.append(cnt).append("\n");
}
System.out.println(sb);
}
private static void dfs(int x, int y) {
isVisited[x][y] = true;
//상하좌우로 인접 위치 탐색
for(int i=0; i<4; i++) {
int nx = x+dx[i];
int ny = y+dy[i];
if(nx>=0 && ny>=0 && nx < n && ny < m) {
if(adjMatrix[nx][ny]==1 && !isVisited[nx][ny]) {
dfs(nx,ny);
}
}
}
}
}