내가 개발해볼게!!
[BOJ] 1012번: 유기농 배추 본문
https://www.acmicpc.net/problem/1012
문제
입력
입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트 케이스에 대해 첫째 줄에는 배추를 심은 배추밭의 가로길이 M(1 ≤ M ≤ 50)과 세로길이 N(1 ≤ N ≤ 50), 그리고 배추가 심어져 있는 위치의 개수 K(1 ≤ K ≤ 2500)이 주어진다. 그 다음 K줄에는 배추의 위치 X(0 ≤ X ≤ M-1), Y(0 ≤ Y ≤ N-1)가 주어진다. 두 배추의 위치가 같은 경우는 없다.
출력
각 테스트 케이스에 대해 필요한 최소의 배추흰지렁이 마리 수를 출력한다.
난이도
실버 2
Sol 1
배추밭 배열을 처음부터 끝까지 돌면서 배추가 있는 곳을 만날 때마다 DFS 재귀함수를 돌려 인접한 배추가 존재하는 위치를 방문 배열에 체크하고, cnt++를 해준다. 배추밭 배열을 끝까지 돌았을 때 최종 cnt 값을 답으로 출력.
해당 풀이에서는 배추밭 배열과 방문 배열을 따로 만들었다.
public class BOJ1012 {
static int M, N, K; // 배추밭의 가로 길이, 세로 길이, 배추가 있는 위치의 개수
static int[][] farm; // 배추밭 배열
static boolean[][] isvisited; // 방문 여부를 체크하기 위한 배열
static int[] dx = {1, -1, 0, 0};
static int[] dy = {0, 0, 1, -1};
static int cnt; // 필요한 배추흰지렁이의 수
public static void main(String[] args) throws IOException {
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
int T = Integer.parseInt(bf.readLine());
for(int i=0; i<T; i++) {
StringTokenizer token = new StringTokenizer(bf.readLine());
M = Integer.parseInt(token.nextToken());
N = Integer.parseInt(token.nextToken());
K = Integer.parseInt(token.nextToken());
farm = new int[M][N];
isvisited = new boolean[M][N];
cnt = 0;
// 매 테스트 케이스마다 배추밭 배열, 방문 배열, cnt를 초기화해줘야 한다
for(int j=0; j<K; j++){
token = new StringTokenizer(bf.readLine());
int x = Integer.parseInt(token.nextToken());
int y = Integer.parseInt(token.nextToken());
farm[x][y] = 1;
}
// input
for(int x=0; x<M; x++){
for(int y=0; y<N; y++){
if(farm[x][y] == 1 && !isvisited[x][y]){ // 배추가 위치해 있고 해당 위치를 방문하지 않았다면
search(x, y); // dfs 메소드를 돌려 (x, y)와 인접해 있는 모든 배추의 위치를 방문 배열에 체크한다.
cnt++; // 배추흰지렁이 카운트를 1 더해준다
}
}
}
// operation
System.out.println(cnt);
// output
}
}
static void search(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 && nx < M && ny >= 0 && ny < N){
if(farm[nx][ny] == 1 && !isvisited[nx][ny]){
search(nx, ny); // 해당 좌표의 인접한 곳에 배추가 존재한다면 dfs 함수를 돌려 체크한다
}
}
}
}
}
Sol 2
위와 같은 풀이에서 방문 배열을 제거하고 배추밭 배열을 boolean 형식으로 만들어 방문 배열처럼 사용했다
public class B1012_유기농배추 {
static int M, N, K; // 배추밭의 가로 길이, 세로 길이, 배추가 있는 위치의 개수
static boolean[][] farm;
static int[] dx = {1, -1, 0, 0};
static int[] dy = {0, 0, 1, -1};
static int cnt;
public static void main(String[] args) throws IOException {
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
int T = Integer.parseInt(bf.readLine());
for(int i=0; i<T; i++) {
cnt = 0;
StringTokenizer token = new StringTokenizer(bf.readLine());
M = Integer.parseInt(token.nextToken());
N = Integer.parseInt(token.nextToken());
K = Integer.parseInt(token.nextToken());
farm = new boolean[M][N];
for(int j=0; j<K; j++){
token = new StringTokenizer(bf.readLine());
int x = Integer.parseInt(token.nextToken());
int y = Integer.parseInt(token.nextToken());
farm[x][y] = true;
}
// input
for(int x=0; x<M; x++){
for(int y=0; y<N; y++){
if(farm[x][y] == true){
search(x, y);
cnt++;
}
}
}
// operation
System.out.println(cnt);
// output
}
}
static void search(int x, int y){
farm[x][y] = false;
for(int i=0; i<4; i++){
int nx = x + dx[i];
int ny = y + dy[i];
if(nx >= 0 && nx < M && ny >= 0 && ny < N){
if(farm[nx][ny] == true){
search(nx, ny);
}
}
}
}
}
😅
시간이나 메모리가 줄어드나 싶어서 방문 배열을 없애봤는데(Sol 2) 오히려 시간이 조금 늘었다.. 왜 그러지? 스터디원들은 시간은 그대로 나오고 메모리가 줄었다고 하는데..
아래쪽이 Sol 1, 위쪽이 Sol 2 코드로 돌린 결과!
'Algorithm > BOJ' 카테고리의 다른 글
[BOJ] 백준 20055번: 컨베이어 벨트 위의 로봇 (0) | 2023.08.23 |
---|---|
[BOJ] 백준 2343번: 기타 레슨(Java) (0) | 2023.08.17 |
[BOJ] 1932번: 정수 삼각형(Java) (0) | 2023.08.10 |
[BOJ] 9465번: 스티커 (0) | 2023.08.08 |
[BOJ] 1495번: 기타리스트(java) (0) | 2023.08.04 |