BOJ/백준 - 1012 유기농 배추 JAVA

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

1012번: 유기농 배추

 

이 문제는 뇌에 힘을 줘서 좌표 생각을 잘 해야 한다. 

가로길이 M, 세로길이 N인데

for문을 돌리거나 Queue에 넣을 때 잘 넣어보자

 

좌표는

1.

arr[x][y]

 

2.

arr[y][x]

 

이걸 보고 참고하자.

나는 2번이 더 익숙해서 2번으로 풀었다.

 

 

DFS로도 풀어보고, BFS로도 풀어봤다.

import java.awt.*;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
 
public class Main {
    static int T,M,N,K;
    static int[][] arr;
    static boolean[][] visit;
    static int[] dx = {0,0,-1,1}; //상,하,좌,우
    static int[] dy = {1,-1,0,0};
    static LinkedList<Integer> res = new LinkedList<>();
    static int cnt=0;
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
 
        T = Integer.parseInt(br.readLine());
 
        while(T!=0){
            T--;
            StringTokenizer st = new StringTokenizer(br.readLine()," ");
            M = Integer.parseInt(st.nextToken());
            N = Integer.parseInt(st.nextToken());
            K = Integer.parseInt(st.nextToken());
 
            arr = new int[N][M];
            visit = new boolean[N][M];
 
            for(int i=0;i<K;i++){
                st=new StringTokenizer(br.readLine()," ");
                int u = Integer.parseInt(st.nextToken());
                int v = Integer.parseInt(st.nextToken());
 
                arr[v][u]=1;
            }
 
            for(int i=0;i<N;i++){
                for(int j=0;j<M;j++){
                    if(!visit[i][j] && arr[i][j]==1){
                        cnt++;
                        //dfs(i,j);
                        bfs(i,j);
                    }
                }
            }
            System.out.println(cnt);
            cnt=0;
        }
    }
    static void dfs(int y,int x){
        visit[y][x]=true;
 
        for(int i=0;i<4;i++){
            //다음 방문할 좌표 구하기
            int nxtx = x+dx[i];
            int nxty = y+dy[i];
            
            //다음 좌표가 범위를 벗어나면
            if(nxtx<0 || nxtx>=M || nxty<0 || nxty>=N) continue;
            //방문하지 않았고, 상하좌우중 배추가 있으면
            if(!visit[nxty][nxtx] && arr[nxty][nxtx]==1){
                dfs(nxty,nxtx);
            }
        }
    }
 
    static void bfs(int y,int x){
        Queue<Point> q = new LinkedList<>();
        //뒤집어서 넣는다.
        q.offer(new Point(y,x));
 
        while(!q.isEmpty()){
            Point cur = q.poll();
            visit[cur.x][cur.y]=true;
 
            for(int i=0;i<4;i++){
                //다음 방문할 좌표 구하기
                //위에서 뒤집어서 넣었으니까, y와 x로 꺼낸다.
                int nxtx= dx[i]+cur.y;
                int nxty= dy[i]+cur.x;
 
                //다음 방문할 좌표 구하기
                if(nxtx<0 || nxtx>=M || nxty<0 || nxty>=N) continue;
                //방문하지 않았고, 상하좌우중 배추가 있으면
                if(!visit[nxty][nxtx] && arr[nxty][nxtx]==1){
                    q.offer(new Point(nxty,nxtx));
                    visit[nxty][nxtx]=true;
                }
            }
        }
    }
}