[백준 3184 | DFS] 양

풀이

맨 처음에 BFS로 문제를 접근했다가 메모리초과가 나서 다시 DFS로 접근했던 문제였다.

DFS로 이 문제를 해결하는 방법은 다음과 같다.

1. 반복문을 돌리면서 '#' 이 아닌 좌표를 찾아 차례로 DFS 함수를 실행한다.

2. DFS 함수 안에서는 우선 해당 좌표의 값이 'v' 인지 'o' 인지, '.' 인지 확인한다.

3. v 인경우 wCnt 값을 증가시키고, '.'로 바꾼다 o인 경우 sCnt 값을 증가시키고 '.'로 바꾼다.

4. 해당 좌표의 상하좌우 값이 Valid 한 좌표인지 확인하고 각각 DFS를 수행한다.

하나의 구역 탐색이 끝나면, sCnt, wCnt를 비교해서 누가 이기는지 판단하고 최종 cnt1, 2값을 증가시키면 된다.

소스코드

import java.util.*;
import java.io.*;
public class BOJ_3184 {
 
    static int n, m, cnt1, cnt2, sCnt, wCnt;
    static char[][] map;
    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));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
 
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        map = new char[n][m];
        for(int i=0;i<n;i++){
            String temp = br.readLine();
            for(int j=0;j<m;j++){ map[i][j] = temp.charAt(j); }
        }
 
        //DFS
        cnt1 = 0; cnt2 = 0;
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                if(map[i][j] != '#'){
                    wCnt = 0; sCnt = 0; DFS(i, j);
                    if(sCnt > wCnt) cnt1+=sCnt;
                    else cnt2 += wCnt;
                }
            }
        }
 
        bw.write(cnt1+" "+cnt2+"\n");
        bw.flush();
        bw.close();
    }
 
    public static void BFS(int a, int b){
        Queue<Coordinate> q = new LinkedList<Coordinate>();
        q.offer(new Coordinate(a, b));
 
        int sCnt = 0; int wCnt = 0;
        while(!q.isEmpty()){
            int x = q.peek().x;
            int y = q.peek().y;
            q.poll();
            if(map[x][y]=='v') wCnt++;
            else if(map[x][y]=='o')sCnt++;
 
            for(int i=0;i<4;i++){
                if(isValid(x+dx[i], y+dy[i]) && map[x+dx[i]][y+dy[i]] != '#'){
                    q.offer(new Coordinate(x+dx[i], y+dy[i]));
                }
            }map[x][y] = '#';
        }
        if(sCnt>wCnt){cnt1+=sCnt;}
        else cnt2+=wCnt;
 
    }
    public static void DFS(int x, int y){
        if(map[x][y] == 'v') wCnt++;
        else if(map[x][y] == 'o') sCnt++;
        map[x][y] = '#';
        for(int i=0;i<4;i++){
            if(isValid(x+dx[i], y+dy[i]) && map[x+dx[i]][y+dy[i]] != '#')
                DFS(x+dx[i], y+dy[i]);
        }
 
    }
 
    public static boolean isValid(int i, int j){
        if(i>=0 && i<n && j>=0 && j<m) return true;
        return false;
    }
    public static void print(){
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                System.out.print(map[i][j]);
            }System.out.println();
        }
    }
}
class Coordinate{
    int x, y;
    Coordinate(int x, int y){
        this.x = x;
        this.y = y;
    }
}