[백준 BOJ/Silver II] 1012번 : 유기농 배추

 

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

1012번: 유기농 배추

import java.util.Scanner;

public class Main {

    // 상하좌우
    static int dx[] = {-1, 1, 0, 0}; // i 움직임 
    static int dy[] = {0, 0, -1, 1}; // j 움직임
    
    static int[][] land; // 전체 땅
    static boolean[][] check; // 지나갔는지 체크
    static int count; // 답 카운트
    static int M; // 가로, j
    static int N; // 세로, i
    static int K; // 배추 심어진 위치 개수, 1 입력되는 개수

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt(); // 테스트케이스
        int index = 0;

        while (index < T) {
            count = 0;
    
            M = sc.nextInt();
            N = sc.nextInt(); 
            K = sc.nextInt();
            land = new int[N][M]; 
            check = new boolean[N][M];
            
            for(int i =0; i<K; i++) {
                int x = sc.nextInt();
                int y = sc.nextInt();
                land[y][x] = 1;   
                check[y][x] = true;
            }


            for(int i=0; i<N; i++) {
                for(int j=0; j<M; j++) {
                    
                    if(check[i][j] == true && land[i][j] == 1) {
                        
                        // 상하좌우 확인하는 dfs 실행
                        dfs(i, j);
                        count++; // 다 확인하고 돌아오면 +1
                    }
                }  
            }

            System.out.println(count); // 답 출력
            index++; // 다음 테스트케이스로 넘김
        }

    }

    static void dfs(int x, int y) {

        check[x][y] = false;

        for(int i=0; i<4; i++) { //상하좌우 확인
            int nextX = x + dx[i];
            int nextY = y + dy[i];

            if(nextX>=0 && nextX<N && nextY>=0 && nextY<M) {

                if(check[nextX][nextY] == true && land[nextX][nextY] == 1) {
                    dfs(nextX, nextY);
                }
            }
        }
    }
}

 

배추가 있는 위치를 1로 표시했고 나중에 1 있는 위치를 확인하고 지나갔다고 표시해줄 boolean 배열에는 1 위치를 true로 넣어주었다 1이 있는 위치에서 상하좌우로 확인하고 다 돌고나서 count를 1씩 올려주면 최종 답이 나온다

 

근데 풀고 나니까 boolean을 따로 쓰기보다는 확인하면 0으로 바꿔주는거로 코드를 줄여도될듯했다

 

import java.util.Scanner;

public class Main {

    // 상하좌우
    static int dx[] = {-1, 1, 0, 0}; // i 움직임 
    static int dy[] = {0, 0, -1, 1}; // j 움직임
    
    static int[][] land; // 전체 땅
    static int count; // 답 카운트
    static int M; // 가로, j
    static int N; // 세로, i
    static int K; // 배추 심어진 위치 개수, 1 입력되는 개수

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt(); // 테스트케이스
        int index = 0;

        while (index < T) {
            count = 0;
    
            M = sc.nextInt();
            N = sc.nextInt(); 
            K = sc.nextInt();
            land = new int[N][M]; 
            
            for(int i =0; i<K; i++) {
                int x = sc.nextInt();
                int y = sc.nextInt();
                land[y][x] = 1;   
            }


            for(int i=0; i<N; i++) {
                for(int j=0; j<M; j++) {
                    
                    if(land[i][j] == 1) {
                        
                        // 상하좌우 확인하는 dfs 실행
                        dfs(i, j);
                        count++; // 다 확인하고 돌아오면 +1
                    }
                }  
            }

            System.out.println(count); // 답 출력
            index++; // 다음 테스트케이스로 넘김
        }

    }

    static void dfs(int x, int y) {

        land[x][y] = 0;

        for(int i=0; i<4; i++) { //상하좌우 확인
            int nextX = x + dx[i];
            int nextY = y + dy[i];

            if(nextX>=0 && nextX<N && nextY>=0 && nextY<M) {

                if(land[nextX][nextY] == 1) {
                    dfs(nextX, nextY);
                }
            }
        }
    }
}

 

통과된다!!

이제 이런문제는 어떻게 풀어야할지 조오오오오오금 감이 온다 더 어려운 문제면 못풀겠지만,,

 

코드를 다 작성하고 분명히 이렇게 하면 맞을거같은데 자꾸 인덱스가 범위를 넘어간다는 오류가 났다 고쳐보다가 반친구한테 코드봐달라고 했는데 정말정말 사소한 실수를 또😐😐

 

그 다음 K줄에는 배추의 위치 X(0 ≤ X ≤ M-1), Y(0 ≤ Y ≤ N-1)가 주어진다. 

라고 되어있는데 land와 check 배열을 채워줄때 [x][y] 순서로 받아버린거다(i를 N, j를 M 기준으로 하고 풀었기 때문에 입력받아줄때 [y][x]로 받아줘야했다)

입력 순서가 어떻게 되는지 꼼꼼하게 확인필요,,!!!!

다음부터는 입력이 제대로 받아와지는지부터 확인해봐야겠다

 

 

 

 

+

2024.02.14

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main {
	static int M;
	static int N;
	static int K;
	static int[][] land;
	static int result;
	static int[] dx = {-1, 1, 0, 0};
	static int[] dy = {0, 0, -1, 1};
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(br.readLine());
		
		int index = 0;
		while(index < T) {
			result = 0;
			String[] str = br.readLine().split(" ");
			M = Integer.parseInt(str[0]);
			N = Integer.parseInt(str[1]);
			K = Integer.parseInt(str[2]);
			land = new int[N][M];
			
			for(int i = 0; i < K; i++) {
				String[] str2 = br.readLine().split(" ");
				int y = Integer.parseInt(str2[0]);
				int x = Integer.parseInt(str2[1]);
				land[x][y] = 1;
			}
			
			//System.out.println(Arrays.deepToString(land));
			
			for(int i = 0; i < N; i++) {
				for(int j = 0; j < M; j++) {
					if(land[i][j] == 1) {
						check(i, j);
						result++;
					}
				}
			}
			
			index++;
			System.out.println(result);
			
		}		
	}
	
	static void check(int x, int y) {
		land[x][y] = 0;
		
		for(int i = 0; i < 4; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			
			if(nx >= 0 && nx < N && ny >= 0 && ny < M) {
				if(land[nx][ny] == 1) check(nx, ny);
			}
		}
	}
}

 

 

https://fruits2lim.tistory.com/entry/%EB%B0%B1%EC%A4%80-BOJSilver-I-2667%EB%B2%88-%EB%8B%A8%EC%A7%80%EB%B2%88%ED%98%B8%EB%B6%99%EC%9D%B4%EA%B8%B0

[백준 BOJ/Silver I] 2667번 : 단지번호붙이기

 

이 문제에 이어서 코테스터디 과제로 한번 더 풀게된 문제!!!

 

 

훨씬 더 빠르고 간결하게 풀 수 있게 됐다👍👍