백준 1303번
https://www.acmicpc.net/problem/1303

---

문제

전쟁은 어느덧 전면전이 시작되었다. 결국 전투는 난전이 되었고, 우리 병사와 적국 병사가 섞여 싸우게 되었다. 그러나 당신의 병사들은 흰색 옷을 입고, 적국의 병사들은 파란색 옷을 입었기 때문에 서로가 적인지 아군인지는 구분할 수 있다. 문제는 같은 팀의 병사들은 모이면 모일수록 강해진다는 사실이다.

N명이 뭉쳐있을 때는 N$^2$ 의 위력을 낼 수 있다. 과연 지금 난전의 상황에서는 누가 승리할 것인가? 단, 같은 팀의 병사들이 대각선으로만 인접한 경우는 뭉쳐 있다고 보지 않는다.

---

입력

첫째 줄에는 전쟁터의 가로 크기 N, 세로 크기 M(1 ≤ N, M ≤ 100)이 주어진다. 그 다음 두 번째 줄에서 M+1번째 줄에는 각각 (X, Y)에 있는 병사들의 옷색이 띄어쓰기 없이 주어진다. 모든 자리에는 병사가 한 명 있다. B는 파란색, W는 흰색이다. 당신의 병사와 적국의 병사는 한 명 이상 존재한다.

---

생각하기

처음 문제 풀이를 고민하던 중 가장 큰 실수가 흰색과 파란색이 하나씩 있을때를 고려해서 따로 계산해야 된다고 생각했었던 부분이 큰 착각이었다.

생각해보면 상 하 좌 우 기준으로 뭉쳐있을 경우 제곱의 위력을 낼 수 있다는 데, 뭉쳐있지 않은 경우 한명만 있어도 상관이 없었다 1의 제곱은 어차피 1 이니까 뭉쳐있을 때의 계산 식을 그대로 사용할 수 있다는 것이었다.

이 후 다른 부분에서 막혀서 다른 분들의 코드를 찾아보았는데 설명이 제대로 나와있는게 없어서 진짜 이해하기 너무 힘들었다..

이 문제의 특징은 상하좌우를 탐색하며 범위를 벗어나지 않게 하기 위해서
미리 x와 y의 배열을 만들어 놓고 시작한다는 점이다.

범위 설정은 간단하다 우리가 아군과 적군이 표시되어 있는 지도(map)에서 탐색 범위가 0 아래로 내려가면 안되고 N,M보다 높으면 지도를 벗어난다는 특징이 있다. 그렇기 때문에 이 지도에서 아군과 적군을 지도에서 탐색할 범위를 미리 계산할 값을 배열로 만들어 주는 것이다.

자세한 설명은 아래에서 설명하도록 하겠다.

dirX = {0, 0, -1, 1}
dirY = {-1, 1, 0, 0}

아래의 DFS와 BFS의 설명은 백준에서 제공하는 아래의 테스트케이스를 예로 설명하겠다.

5 5
WBWWW
WWWWW
BBBBB
BBBWW
WWWWW

DFS

DFS는 재귀함수로 문제를 풀었다.
앞 부분 실행만 이해하면 뒤에서도 간단하게 풀 수 있다.

먼저 여기서 i가 세로이고 j가 가로임을 미리 헷갈리지말자
지도를 표시할 map과 방문 여부를 표시할 visit 배열을 미리 초기화 한 후의 실행이다.

반복문에서 i,j가 0으로 시작, color는 'W'가 되어
DFS(0, 0, 'W') 로 시작한다.

DFS는 재귀이기 때문에 한번 실행되면 범위내에서 다른 색깔이 나올 때까지 DFS를 계속돌고, Main문 으로 다시 돌아오지 않는다.

DFS의 코드를 보면
처음 들어오는 값은 방문을 했다는 의미로 visit을 true 처리해 준다.

그럼 x는 0 y는 0으로 visit[0][0]은 true값이 되고 현재의 위치를 계산하기 위해
now_x, now_y 를 활용한다. 현재 위치 0, 0에서 상하 좌우 4개를 계산해야 하기 때문에 x y는 그대로 두고 now_x, now_y를 따로 계산하는 것이다.

이제 이now_x, now_y 로 범위를 계산한다

범위 계산은 now_y 부터 보면 위 아래를 계산하니 상 하 좌 우 기준에 상은 -1이고 하는 1이다
우리는 0 0부터 시작하니 위로 올라가면 안되기 때문에 -1 + 0을 했을 경우 now_y는 -1이 된다
이러면 0보다 아래 이기때문에 범위를 벗어나서 이 범위는 탐색을 하지 못하고
1 + 0의 경우는 1이기때문에 범위를 벗어나지 않아서 아래쪽을 탐색할 수 있는 것이다.

이렇게 Range_check() 함수를 통해 now_x, now_y 둘 다 범위를 벗어나지 않는 값으로

다시 DFS()함수를 돌린다 이 재귀 과정을 반복해서map[now_y][now_x]에서 'B'가 모두나오면서 하나씩 종료되면 결국 빠져나오게 된다.

다시 Main문으로 돌아오면 다시 i=0, j=1가 된다 다음 코드에서 map[0][1] = 'B'가 되기 때문에 DFS(1, 0, 'B')으로 실행한다. 이때 'B'는 중간에 하나만 끼워 있기 때문에 색깔이 달라서 바로 재귀를 하지 않고 DFS를 빠져나오게 된다.

이게 DFS의 반복이다.
뜯어보면 어렵지 않은 반복일 뿐인데 처음보니 정말 까다롭고 어렵게 느껴진다.

BFS

다음은 BFS인데 BFS는 DFS와 다르게 Queue 자료구조를 사용해서 풀어간다.

여기서 que를 사용할때 x,y를 모두 사용해야 하기 때문에 좌표 클래스 Node를 만들어줬다.

BFS는 범위를 넓혀가면서 탐색한다
일단, 위에서 설명한 DFS와 i,j 순서는 같다

그러나 색깔이 같고, 방문한적이 없으며, 범위 안에 있는 경우 이 now_x와 now_y값을 que 집어 넣고 BFS를 실행해서 넘어가지 않고 다음 now_x와 now_y가 조건에 부합하는지 검사하며 que에 넣을지 말지를 결정한다.

이렇게 que에 집어넣고 빼기를 반복하며 que가 비면 다시 Main으로 돌아온다.

이 과정을 반복하면 결국 모든 반복문을 마치고 종료된다.

TMI

한 동안은 DFS와 BFS 위주로 공부를 좀 해야할 것 같다
계속 개념도 잡아가면서 문제를 푸는데도

이해가 잘안되고 다른사람들의 코드를 봐도 이해가 안된다
1만시간의 법칙을 적용한다면 괜찮아지지 않을까라고 조심스럽게 생각해본다...

---

코드

DFS 사용

import java.util.*;
import java.io.*;

public class Main {
	static int N; // 가로
	static int M; // 세로
	static int now_x;
	static int now_y;
	static int count = 0;

	static int white_count = 0;
	static int black_count = 0;
	static char map[][];
	static boolean visit[][];

	// 상 하 좌 우 범위 체크에서 사용할 배열 
	static int dirY[] = {-1, 1, 0, 0}; // 상 하 체크
	static int dirX[] = {0, 0, -1, 1}; // 좌 우 체크

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;

		st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken()); // 가로 
		M = Integer.parseInt(st.nextToken()); // 세로

		// 1. 지도 만들기
		map = new char[M][N];
		visit = new boolean[M][N];
		for(int i=0; i<M; i++) {
			String str = br.readLine();
			for(int j=0; j<N; j++) {
				char ch = str.charAt(j);
				map[i][j] = ch; 
			}
		}

		// 2. DFS를 이용해서 탐색하기.
		for(int i=0; i<M; i++) { // 세로
			for(int j=0; j<N; j++) { // 가로

				if(visit[i][j] == false) {
					char color = map[i][j];
					count = 0;
					DFS(j, i, color);

					if(color == 'W') {
						white_count += count * count;
					}
					else {
						black_count += count * count;
					}
				}
		

			}
		}

		System.out.println(white_count + " " + black_count);

	}// End of main

	static void DFS(int x, int y, char color) {
		visit[y][x] = true;
		count += 1;

		for(int i=0; i<4; i++) {
			now_y = y + dirY[i];
			now_x = x + dirX[i];

			if(Range_check() == true && map[now_y][now_x]==color && visit[now_y][now_x] == false ) {
				DFS(now_x, now_y, map[now_y][now_x]);
			}

		}

	}// End of DFS		

	static boolean Range_check() {
		return (0 <= now_y && now_y < M && 0 <= now_x && now_x < N);
	}
	
}

---

BFS 사용

import java.util.*;
import java.io.*;

public class Main{
	static int N; // 가로
	static int M; // 세로
	static int count;
	static int white_count = 0;
	static int black_count = 0;

	static Queue<Node> que = new LinkedList<>();
	static int dy[] = {-1, 1, 0, 0}; // 상 하 좌 우
	static int dx[] = {0, 0, -1, 1}; // 상 하 좌 우
	static boolean Visited_arr[][];
	static char map[][];

	// Queue에 x, y좌표를 담기위해 만든 생성자 
	static class Node {
		int x;
		int y;

		public Node(int y, int x) {
			this.y = y;
			this.x = x;
		}
	} // End Node

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken()); // 가로
		M = Integer.parseInt(st.nextToken()); // 새로

		// 방문 여부를 체크하는 배열
		Visited_arr = new boolean[M][N];

		// 흰색과 파란색을 넣을 만들 지도 (배열)
		map = new char[M][N];
		for(int i=0; i<M; i++) {
			st = new StringTokenizer(br.readLine());
			String temp = st.nextToken();

			for(int j=0; j<N; j++) {
				char ch = temp.charAt(j);
				map[i][j] = ch;
			}
		}

		// 2차원 배열 순환
		for(int i=0; i<M; i++) {
			for(int j=0; j<N; j++) {

				// false -> 방문한적이없는 곳일 경우
				if( Visited_arr[i][j] == false) {
		
					if(map[i][j] == 'W') {
						int num = BFS(i, j, 'W');
						white_count += num * num;
					}
					else {
						int num = BFS(i, j, 'B');
						black_count += num * num;
					}

				}
			}
		}

		System.out.println(white_count + " " + black_count);
	} // End main
	
	static int BFS(int y, int x, char ch) {
		que.offer(new Node(y, x));
		count = 1;
		Visited_arr[y][x] = true;

		// BFS특성 Queue가 빌때 까지 계속해서 반복
		while( !que.isEmpty() ) {
			// 들어온 값을 que에서 하나 빼냄
			Range_check(ch); 
		}

		return count;
	} // End Function BFS
	

	static void Range_check(char ch) {
		// x y 좌표 두가지를 담기위해 Node형으로 Queue를 만들음
		Node now = que.poll();

		for(int i=0; i<4; i++) {

			int now_y = now.y + dy[i];
			int now_x = now.x + dx[i];

			if(now_y >= 0 && now_y<M && now_x>=0 && now_x<N) {

				if(Visited_arr[now_y][now_x] == false && ch == map[now_y][now_x] ) {

					que.offer(new Node(now_y, now_x));
					Visited_arr[now_y][now_x] = true;
					count++;
				}

			}	
		} //End for
	} // End Range_check

} // End Class