(JAVA) [BOJ]백준 1012번, 유기농배추

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

1715번: 카드 정렬하기

1012, 유기농배추

[ 난이도 : 실버 2 ]

이번 문제는 그래프 탐색 & DFS 를 사용하여 풀어보겠다.

# Process

main

: 이번 문제에서 주의해야 할 것은 좌표를 (0,1) (1,3) 과 같이 주는데 가로&세로의 범위를 잘 생각해야 한다.

지역을 나타내는 area 와 방문 여부를 확인하는 visit 배열을 먼저 생성해주고 배추의 위치는 area 에 값을 1로 설정해준다.

 

static boolean[][] visit;
static int T,M,N,K;
static int[][] area;
static int[][] dir = {{1,0},{-1,0},{0,1},{0,-1}};

static void input() 
{
    M = scan.nextInt();  // 가로길이
    N = scan.nextInt();  // 세로길이
    K = scan.nextInt();  // 배추개수
    area  = new int[N][M];
    visit = new boolean[N][M];

    // 배추심기
    while(K-- >0)
    {
        int y = scan.nextInt();
        int x = scan.nextInt();
        area[x][y] = 1;
    }
}

 

순회

: 지역을 순회하면서 배추의 위치에서 dfs 를 탐색해서 이어진 부분을 모두 visit = true 로 만들어주고, 한번의 순회에 카운트 값을 더해주면 된다.

더한 값을 sb 에 append 해주고 테스트 케이스가 종료된 후, sb 값을 출력해주면 된다.

static void pro() 
{
    int cnt = 0;
    for(int i=0; i<N; i++)
    {
        for(int j=0; j<M; j++)
        {
            if(area[i][j] == 1 && !visit[i][j])
            {
                cnt++;
                dfs(i,j);
            }
        }
    }
    sb.append(cnt+"\n");
}

 

DFS

: 함수가 호출되면 해당 x, y 좌표에 방문 표시를 해준다. 

그 후, 상하좌우를 이동하며 이동이 가능하다면 재귀로 dfs 를 호출해나가며 인접한 배추의 위치를 모두 찾는다.

static void dfs(int x, int y)
{
    visit[x][y] = true;

    for(int i=0; i<4; i++)
    {
        int nx = x + dir[i][0];
        int ny = y + dir[i][1];

        // 범위를 넘어가는가
        if(nx<0 || ny<0 || nx>=N || ny>=M) continue;
        // 배추가 있는가
        if(area[nx][ny] == 0) continue;
        // 방문했던 곳인가
        if(visit[nx][ny]) continue;

        dfs(nx, ny);
    }
}

 

전체코드

static FastReader scan = new FastReader();
static StringBuilder sb = new StringBuilder();

static boolean[][] visit;
static int T,M,N,K;
static int[][] area;
static int[][] dir = {{1,0},{-1,0},{0,1},{0,-1}};

static void input() 
{
    M = scan.nextInt();  // 가로길이
    N = scan.nextInt();  // 세로길이
    K = scan.nextInt();  // 배추개수
    area  = new int[N][M];
    visit = new boolean[N][M];

    // 배추심기
    while(K-- >0)
    {
        int y = scan.nextInt();
        int x = scan.nextInt();
        area[x][y] = 1;
    }
}

static void pro() 
{
    int cnt = 0;
    for(int i=0; i<N; i++)
    {
        for(int j=0; j<M; j++)
        {
            if(area[i][j] == 1 && !visit[i][j])
            {
                cnt++;
                dfs(i,j);
            }
        }
    }
    sb.append(cnt+"\n");
}

static void dfs(int x, int y)
{
    visit[x][y] = true;

    for(int i=0; i<4; i++)
    {
        int nx = x + dir[i][0];
        int ny = y + dir[i][1];

        // 범위를 넘어가는가
        if(nx<0 || ny<0 || nx>=N || ny>=M) continue;
        // 배추가 있는가
        if(area[nx][ny] == 0) continue;
        // 방문했던 곳인가
        if(visit[nx][ny]) continue;

        dfs(nx, ny);
    }
}


public static void main(String[] args) 
{
    T = scan.nextInt();
    while(T-- > 0)
    {
        input();
        pro();
    }
    System.out.println(sb.toString());
}

 

 

급하게 조사하고 정리하다보니 부족하거나 틀린 내용이 있을 수도 있는데 댓글로 달아주시면 감사하겠습니다!