[백준 1303] 전쟁 - 전투

[백준 1303] 전쟁 - 전투

현대오토에버 코딩테스트를 위한 재활 훈련, 그 막바지.
그래프로 돌아와 DFS와 BFS의 기본을 다잡고자 이 문제를 풀었다.
사실 처음엔 그래프 문제인지 모르고 일단 선택한 문제였는데, 얼떨결에 얻어걸렸다.

문제는 매우 간단하다.
쭉 이차원 배열을 탐색하며 같은 군대끼리 붙어있으면 하나씩 더해주면 되는 간단한 그래프 탐색문제이다.

그래프에서 붙어있는 정점을 찾기 위한 방법 중 가장 먼저 생각나는 것은?
기억이 안나다가도 자동으로 손이 마구 타자를 쳐버리는 '상하좌우',
델타 탐색이다.

델타 탐색에서 꼭 기억해야할 것들을 다시 짚자면,

1. 탐색 시 갈 수 없는 부분인지 반드시 검증해야한다. (N < 0, N >= max 시 탐색하면 안된다.)
2. row와 column 구분을 헷갈리지 마라. (dr, dc, dx, dy 변수 명칭에 주의)

이러하다.
일단 이 문제는 DFS로도 풀 수 있고, BFS로도 풀 수 있다.
두 방법 모두 확인해보자.

📌 DFS

DFS에서 기억해야할 것

1. 한번 확인한 정점은 반드시 방문 체크를 해야한다.
2. 첫 정점부터 마지막 정점까지 순회하며 방문 체크가 되어있지 않은 정점을 모두 세어야한다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class Main {
	static String [][] war;
	static int N;
	static int M;
	//상하좌우
	static int dc [] = {0, 0, -1, 1};
	static int dr [] = {-1, 1, 0, 0};
	static boolean [][] flag;
	static int mine = 0;
	static int mineAttack = 0;
	static int enemy = 0;
	static int enemyAttack = 0;
	
	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());
		
		war = new String [M][N];
		flag = new boolean [M][N];
		
		for(int i = 0; i < M; i++) {
			String [] line = br.readLine().split("");
			for(int j = 0; j < N; j++) {
				war[i][j] = line[j];
			}
		}
		
		for(int i = 0; i < M; i++) {
			for(int j = 0; j < N; j++) {
				if(!flag[i][j]) {
					dfs(war[i][j], j, i);
					if(war[i][j].equals("B")) {
						enemyAttack += enemy * enemy;
						enemy = 0;
					} else {
						mineAttack += mine * mine;
						mine = 0;
					}
				}
			}
		}
		
		bw.write(String.valueOf(mineAttack) + " " + String.valueOf(enemyAttack));
		bw.close();
		br.close();
	}
	
    //dfs
	static void dfs(String soldier, int x, int y) {
		flag[y][x] = true;
		if(soldier.equals("W")) mine++;
		else enemy++;
		
		for(int i = 0; i < 4; i++) {
			int dx = x + dc[i];
			int dy = y + dr[i];
			
			if(isRange(dy, dx) && !flag[dy][dx] && war[dy][dx].equals(soldier)) {
				dfs(soldier, dx, dy);
			}
		}
	}
	
    //델타 검증
	public static boolean isRange(int nr ,int nc) {
		return !(nr < 0 || nr >= M || nc < 0 || nc >= N);
	}
}

📌 BFS

BFS에서 기억해야할 것

1. Queue 활용 시 무한 루프에 빠지지 않게 주의하라.
2. Node 클래스를 따로 구현하여 사용 시, 간선과 가중치 구성에 주의하라. (이 곳에서 가중치는 없다.)
3. DFS와 마찬가지로 방문 체크를 필히 해야한다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

//정점 클래스
class Node {
	int x;
	int y;
	
	public Node(int x, int y) {
		this.x = x;
		this.y = y;
	}
}

public class Main {
	static String [][] war;
	static int N;
	static int M;
	//상하좌우
	static int dc [] = {0, 0, -1, 1};
	static int dr [] = {-1, 1, 0, 0};
	static boolean [][] flag;
	static Queue<Node> q = new LinkedList<>();
	static int mine = 0;
	static int mineAttack = 0;
	static int enemy = 0;
	static int enemyAttack = 0;
	
	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());
		
		war = new String [M][N];
		flag = new boolean [M][N];
		
		for(int i = 0; i < M; i++) {
			String [] line = br.readLine().split("");
			for(int j = 0; j < N; j++) {
				war[i][j] = line[j];
			}
		}
		
		for(int i = 0; i < M; i++) {
			for(int j = 0; j < N; j++) {
				if(!flag[i][j]) {
					bfs(war[i][j], j, i);
					if(war[i][j].equals("B")) {
						enemyAttack += enemy * enemy;
						enemy = 0;
					} else {
						mineAttack += mine * mine;
						mine = 0;
					}
				}
			}
		}
		
		bw.write(String.valueOf(mineAttack) + " " + String.valueOf(enemyAttack));
		bw.close();
		br.close();
	}
	
    //bfs
	static void bfs(String soldier, int x, int y) {
		q.add(new Node(x, y));
		flag[y][x] = true;
		
		while(!q.isEmpty()) {
			Node n = q.poll();
			
			if(soldier.equals("W")) mine++;
			else enemy++;
			
			for(int i = 0; i < 4; i++) {
				int dx = n.x + dc[i];
				int dy = n.y + dr[i];
				
				if(isRange(dy, dx) && !flag[dy][dx] && war[dy][dx].equals(soldier)) {
					flag[dy][dx] = true;
					
					q.add(new Node(dx, dy));
				}
			}
		}
	}
	
    //델타 검증
	public static boolean isRange(int nr ,int nc) {
		return !(nr < 0 || nr >= M || nc < 0 || nc >= N);
	}
}

DFS와 BFS, 델타 탐색은 한번 코드를 외워두면 크게 틀을 벗어나는 법이 없다.
외워두면 유용하게 계속 써먹을 수 있는 코드이다.