[JAVA] 27737번 - 버섯 농장

문제 탐색하기

- 문제에서 구해야 하는 최종 정답은 무엇인지 탐색한 과정
- 그 정답을 구하기 위해 어떻게 코드를 구현해야 할지 고민한 과정
- 문제에 들어오는 범위를 파악하여 어떤 알고리즘을 쓸 수 있을지 고민해 가는 과정

 

계속 10점이 나와서 진짜 어려웠다...ㅎ

 

처음에 생각했던 알고리즘

빨간 화살표 에서 출발해서 K번까지만 탐색을 하고 종료하는방식

-> 다음 탐색지점은 어떻게 할것인가?

적절하지 않아서 탈락

최종 선택 알고리즘

DFS/BFS 문제를 여러번 풀다보니 인접한 지역끼리의 갯수를 세는걸 주로 썼는데 이걸 활용한다.

그림에서 보면 총 4개의 지역이 있다. 그리고 4개의 지역은 각 4,3,4,1개의 땅으로 나뉜다

이걸 활용한다 K는 2라고 가정한다 

4개 -> 2개의 포자가 필요

3개 -> 2개의 포자가 필요

3개 -> 2개의 포자가 필요

1개 -> 1개의 포자가 필요

즉 땅의 갯수를 K로 나누고 올림을 해준다

(region+k-1)/k;

이렇게 일반화할 수 있다. 

 

DFS사용

그리고 DFS를 사용하여 한번 탐색할때마다 그 탐색 영역의 땅의 갯수를 카운팅해준다.

 

버섯 심기 불가능한 경우

불가능한 경우가 있다. 

사용된 포자 개수가 0개일때

사용된 포자 개수가 M개이하 -> 가능한 경우

사용된 포자 개수가 M개 초과

 

시간복잡도

O(N*N)이다 N이 100이니까 충분하다 

 

=> 포자 개수 구하기 + DFS연산으로 인접한 땅 갯수 구하기(메서드) + 지도 모두 탐색하면서 확인하고 정답구하기

 

이렇게 3개로 나눠서 생각하면 조금 더 쉽게 풀 수 있다.

나는 나눠서 생각을 못해서 좀 어려웠다

이렇게 나눠서 생각을 해봐야겠다 

코드 설계하기

위의 문제 탐색하기에서 고민한 과정을 토대로 문제 풀이에 대한 실마리를 잡았다면, 문제 풀이를 본격적으로 하기전, 문제를 풀이 위한 로드맵을 그려본다
어떤 순서로 코드를 작성해야 할지, 어떤 함수들을 작성해야 할지 등을 작성

1. 입력받는다

2. 땅의 갯수를 구하는 탐색을 한다

3. 모든 구역을 탐색한다

4. 포자 개수 구한다

5. 출력 

 

 

시도 회차 수정 사항

- 무분별하게 "맞았습니다" 가 나올때까지 수정하는 형태의 문제 풀이를 반복하면, 내가 어떤 실수를 해서 해당 문제를 틀렸는지 모르게 된다
- 틀렸습니다를 받았다면 왜 틀렸는지 고민핸보고, 어떻게 수정할 수 있는지 고민하는 과정을 작성
- 위에 내가 세울 설계에서 어떤 부분이 틀렸는지도 함께 점검

 

10점짜리 

=> DFS메서드랑 포자개수구하는것은 문제가 없는데 자꾸 10점이라고 뜬다 ㅜ

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
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 boolean[][] isVisited;
	static int[][] arr;
	static int n,m,k,cnt,ans;
	static int[] dx = {-1,1,0,0};
	static int[] dy = {0,0,-1,1};
	

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));	
        
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        k = Integer.parseInt(st.nextToken());
        
        arr = new int[n][n];
        isVisited = new boolean[n][n];
        
        for(int i=0; i<n; i++) {
        	st = new StringTokenizer(br.readLine());
        	for(int j=0; j<n; j++) {
        		arr[i][j] = Integer.parseInt(st.nextToken());
        	}
        }
        
        List<Integer> li = new ArrayList<>();
        int total=0;
        
        for(int i=0; i<n; i++) {
        	for(int j=0; j<n; j++) {
        		if(arr[i][j]==0 && !isVisited[i][j]) {
        			int region = dfs(i,j);
        			li.add(region);
        			total+=region;
        		}
        		
        	}
        }
        if(total ==0) {
        	System.out.println("IMPOSSIBLE");
        	return;
        }
        
        int ans = 0;
        for(int i : li) {
        	ans+=(i+k-1)/k;
        }
        
        if(ans<m) {
        	System.out.println("POSSIBLE");
        	System.out.println(m-ans);
        }
        else {
        	System.out.println("IMPOSSIBLE");
        }
       
        
    }


	private static int dfs(int x, int y) {

		isVisited[x][y] = true;
		int size = 1;

		
		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 < n && arr[nx][ny] == 0 && !isVisited[nx][ny]) {
                size += dfs(nx,ny);
            }
			
			
		}
		return size;
	}	
}

 

정답코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
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 boolean[][] isVisited;
	static int[][] arr;
	static int n,m,k,cnt,ans;
	static int[] dx = {-1,1,0,0};
	static int[] dy = {0,0,-1,1};
	

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));	
        
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        k = Integer.parseInt(st.nextToken());
        
        arr = new int[n][n];
        isVisited = new boolean[n][n];
        
        for(int i=0; i<n; i++) {
        	st = new StringTokenizer(br.readLine());
        	for(int j=0; j<n; j++) {
        		arr[i][j] = Integer.parseInt(st.nextToken());
        	}
        }
        
        
        
        int cnt=0;
        for(int i=0; i<n; i++) {
        	for(int j=0; j<n; j++) {
        		if(arr[i][j]==0 && !isVisited[i][j]) {
        			int region = dfs(i,j);
        			cnt+=(region+k-1)/k;
        		}
        		
        	}
        }
        if(cnt==0) {
        	System.out.println("IMPOSSIBLE");
        }
        else {
        	if(cnt<=m) {
        		System.out.println("POSSIBLE");
        		System.out.println(m-cnt);
        	}
        	else {
        		System.out.println("IMPOSSIBLE");
        	}
        }
       
        
    }


	private static int dfs(int x, int y) {

		isVisited[x][y] = true;
		int size = 1;

		
		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 < n && arr[nx][ny] == 0 && !isVisited[nx][ny]) {
                size += dfs(nx,ny);
            }
			
			
		}
		return size;
	}	
}