(JAVA) [BOJ]백준 3184번, 양

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

1715번: 카드 정렬하기

3184, 양

[ 난이도 : 실버 1 ]

이번 문제는 그래프 탐색과 BFS & DFS를 사용해서 풀어보겠다.

우선적으로 DFS 를 사용해서 풀어보겠다.

# Process

main

: R 과 C 기반으로 전체좌표를 String[][] 의 area 라는 변수에 담아주고 방문 여부를 체크할 visit 을 생성해준다.

static void input() 
{
    R = scan.nextInt(); C = scan.nextInt();
    area = new String[R][C];
    visit = new boolean[R][C];
    for(int i=0; i<R; i++) {
        String str = scan.nextLine();
        for(int j=0; j<C; j++) {
            area[i][j] = String.valueOf(str.charAt(j));
        }
    }
}

순회

: 전체 좌표를 순회하며 "#" 가 아니고 방문하지 않은 좌표에 대한 지역을 dfs 로 탐색해준다.

여기서 탐색 과정에 사용할 tSheep 과 tFox 를 선언해준다. 이는 해당 지역에 양과 늑대의 수를 측정할

변수이고 이것을 기반으로 최종적으로 사용할 Sheep 과 Fox 에 수를 정해줄 것이다.

 

정리하면 해당 지역을 dfs(깊이 우선 탐색) 을 통해 탐색하고 해당 지역의 양과 늑대의 수를 측정한 후, 

양의 수가 더 많다면 양의 수를 Sheep 에 더해주고 반대의 경우 늑대의 수를 Fox 에 더해준다.

static void pro()
{
    for(int i=0; i<R; i++) {
        for(int j=0; j<C; j++) {
            if(!area[i][j].equals("#") && !visit[i][j])
            {
                tSheep = 0;
                tFox = 0;
                dfs(i,j);

                if(tSheep == 0 && tFox == 0) continue;

                if(tSheep > tFox)
                    Sheep += tSheep;
                else
                    Fox += tFox;
            }
        }
    }

    System.out.println(Sheep+" "+Fox);
}

DFS

: 우선 해당 좌표를 방문처리를 진행해준다. "#" 가 아닌 좌표에 대한 탐색이 진행되기 때문에

늑대와 양인지에 대한 확인을 바로 해준다.

 

// 늑대면
if(area[x][y].equals("v")) tFox += 1;
// 양이면
if(area[x][y].equals("o")) tSheep += 1;

그 후에 상하좌우를 이동해가며 3가지 예외처리를 진행한다.

1. 범위를 벗어나는가

2. 이동할 좌표가 울타리인가

3. 이미 방문한 곳인가

 

이 세가지 예외처리를 한 후, 재귀호출을 진행해주며 해당 지역을 조회한다.

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

    // 늑대면
    if(area[x][y].equals("v")) tFox += 1;
    // 양이면
    if(area[x][y].equals("o")) tSheep += 1;

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

        // 범위 ?
        if(nx<0 || ny<0 || nx >=R || ny >=C) continue;
        // 울타리 ?
        if(area[nx][ny].equals("#")) continue;
        // 방문 ?
        if(visit[nx][ny]) continue;

        dfs(nx, ny);
    }
}

전체 코드

: 위의 과정을 통해 울타리안의 지역에서 늑대와 양의 수를 측정하여 Sheep 과 Fox 의 수를 더해간 후 

출력해주면 된다.

static int[][] dir = {{1,0},{-1,0},{0,1},{0,-1}};
static int R,C;
static int Sheep,Fox,tSheep,tFox;
static String[][] area;
static boolean[][] visit;

static void input() 
{
    R = scan.nextInt(); C = scan.nextInt();
    area = new String[R][C];
    visit = new boolean[R][C];
    for(int i=0; i<R; i++) {
        String str = scan.nextLine();
        for(int j=0; j<C; j++) {
            area[i][j] = String.valueOf(str.charAt(j));
        }
    }
}

static void pro()
{
    for(int i=0; i<R; i++) {
        for(int j=0; j<C; j++) {
            if(!area[i][j].equals("#") && !visit[i][j])
            {
                tSheep = 0;
                tFox = 0;
                dfs(i,j);

                if(tSheep == 0 && tFox == 0) continue;

                if(tSheep > tFox)
                    Sheep += tSheep;
                else
                    Fox += tFox;
            }
        }
    }

    System.out.println(Sheep+" "+Fox);
}

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

    // 늑대면
    if(area[x][y].equals("v")) tFox += 1;
    // 양이면
    if(area[x][y].equals("o")) tSheep += 1;

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

        // 범위 ?
        if(nx<0 || ny<0 || nx >=R || ny >=C) continue;
        // 울타리 ?
        if(area[nx][ny].equals("#")) continue;
        // 방문 ?
        if(visit[nx][ny]) continue;

        dfs(nx, ny);
    }
}

public static void main(String[] args) 
{
    input();
    pro();
}

 

# BFS 를 사용한 풀이

: BFS 를 사용한 풀이는 DFS 에서 순회의 과정에서 DFS를 호출한 후,  tSheep 과 tFox 에 따라 값을 변경하는 과정을

BFS 함수 내부에서 처리해주기만 하면 된다.

static int[][] dir = {{1,0},{-1,0},{0,1},{0,-1}};
static int R,C;
static int Sheep,Fox;
static String[][] area;
static boolean[][] visit;

static void input() 
{
    R = scan.nextInt(); C = scan.nextInt();
    area = new String[R][C];
    visit = new boolean[R][C];
    for(int i=0; i<R; i++) {
        String str = scan.nextLine();
        for(int j=0; j<C; j++) {
            area[i][j] = String.valueOf(str.charAt(j));
        }
    }
}

static void pro()
{
    for(int i=0; i<R; i++) {
        for(int j=0; j<C; j++) {
            if(!area[i][j].equals("#") && !visit[i][j])
            {
                bfs(i,j);
            }
        }
    }

    System.out.println(Sheep+" "+Fox);
}

static void bfs(int x, int y)
{
    int tSheep = 0;
    int tFox = 0;
    visit[x][y] = true;

    Queue<Integer> Q = new LinkedList<>();
    Q.add(x);
    Q.add(y);

    while(!Q.isEmpty())
    {
        int qx = Q.poll();
        int qy = Q.poll();

        // 늑대면
        if(area[qx][qy].equals("v")) tFox += 1;
        // 양이면
        if(area[qx][qy].equals("o")) tSheep += 1;

        for(int k=0;k<4;k++)
        {
            int nx = qx + dir[k][0];
            int ny = qy + dir[k][1];

            // 범위 ?
            if(nx<0 || ny<0 || nx >=R || ny >=C) continue;
            // 울타리 ?
            if(area[nx][ny].equals("#")) continue;
            // 방문 ?
            if(visit[nx][ny]) continue;

            visit[nx][ny] = true;

            Q.add(nx);
            Q.add(ny);
        }
    }

    // 이 범위 안에 양도 늑대도 없는 경우
    if(tSheep == 0 && tFox == 0) return;

    if(tSheep > tFox)
        Sheep += tSheep;
    else
        Fox += tFox;

}

public static void main(String[] args) 
{
    input();
    pro();
}

 

두 풀이의 차이는 그렇게 크지 않은 것 같으나, DFS & BFS 로 모두 풀어볼 수 있는 재미있는 문제였던 것 같다.

 

BFS

메모리 : 23,704KB / 시간 : 252ms

DFS

메모리 : 22,144KB / 시간 : 224ms