[ALGO#3] 백준_1303_실버1_전쟁-전투 : DFS와 BFS [JAVA]

문제링크 : https://www.acmicpc.net/problem/1303

1303번: 전쟁 - 전투

삼성 역량평가 IM 수준의 대표 문제입니다.

4방탐색과 BFS, DFS를 이용하는 (2차원 배열) 그래프 탐색문제이다.

백준 게시판을 살펴보니, 이 문제의 가로, 세로 입력을 잘못해서 물어보는 경우가 많았다.

 

public class 이차원배열 {

	public static void main(String[] args) {
		int N = 4; // 가로
		int M = 2; // 세로
		int [][] arr = new int[M][N];
		// 2차원 배열 (1)
		for (int i = 0; i < M; i++) {
			for (int j = 0; j < N; j++) {
				System.out.print(arr[i][j]);
			}
			System.out.println();
		}
		System.out.println();
		// 2차원 배열 (2)
		for (int i = 0; i < arr.length; i++) {
			for (int j = 0; j < arr[i].length; j++) {
				System.out.print(arr[i][j]);
			}
			System.out.println();
		}
	}
}

----- 출력 값-------
0000
0000

0000
0000

 

저는 DFS로 이 문제를 풀었습니다. 

이 문제를 푸는 단계는 크게 3단계이다.

1, 입력 받기

2. 이차원 배열의 모든 요소마다 DFS 돌리기
3. DFS에서 방문체크와 경계값 체크하면서 color 값 세기

 

입력 받기

가로, 세로를 입력받아 2차원 배열의 요소에 값 넣는다.

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	StringTokenizer st = new StringTokenizer(br.readLine());
	// 가로
	N = Integer.parseInt(st.nextToken());
	// 세로
	M = Integer.parseInt(st.nextToken());
	
	map = new char[M][N];
	visited  = new boolean[M][N];
	
	// 1. 입력
	for (int i = 0; i < M; i++) {
		String str = br.readLine();
		for (int j = 0; j < N; j++) {
			map[i][j] = str.charAt(j);
		}
	}

 

 

 

이차원 배열의 모든 요소마다 DFS 돌리기

현재 요소의 컬러 값(아군 : 흰색, 적군 : 블루)을 전역으로 관리해서 dfs로 돌리고 나온 색 개수를 더해준다.

int bCount = 0, wCount = 0;
	
	// 2. 모든 지점마다 최대 count 반환 방법 for문
	for (int i = 0; i < M; i++) {		
		for (int j = 0; j < N; j++) {
			// 현재 컬러 
			cur_color = map[i][j];
			sum = 0;
			dfs(i, j); // (y,x)
			if(cur_color=='B') bCount+= (sum*sum);
			else wCount+=(sum*sum);
		}
	}
		System.out.println(wCount + " " + bCount);
}

 

 

 

 

DFS에서 방문체크와 경계값 체크하면서 color 값 세기

4방 탐색(위, 아래, 오른쪽, 왼쪽 이동)할 때 경계 값 체크를 잘해줘야 한다.

private static void dfs(int y, int x) {
		
		
		// 1) 종료 조건 : 이미 방문 했던 곳이나 현재 컬러가 다음 컬러랑 다르면 종료
		if(visited[y][x] == true ||cur_color != map[y][x]) return;
		
		// 2. 로직 : 색깔이 같다면 방문 체크
		visited[y][x] = true;
		sum++;
	
		// (map이니깐 여기서 경계값 체크하기-> 넘어가도 되는지) 
		// 4방탐색	
		if(y < M-1) dfs(y+1, x); // 아래
		if(x < N-1) dfs(y, x+1); // 오른쪽
		if(x > 0) dfs(y, x-1); //왼쪽
		if(y > 0) dfs(y-1, x); // 위
	}

 

 

 

전체 코드 (JAVA)

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

public class Main {
	
	/**
	 * 메모리  : 12660 KB
	 * 시간   : 88 ms
	 */
	// DFS 돌릴 때 매개변수로 넘기는 것이 불편해서 static 관리했습니다.
    // sum은 dfs() 함수가 void로 짜서 static 관리했습니다. 
	static int M, N;
	static char[][] map;
	static boolean [][] visited;
	static char cur_color;
	static int sum;
	public static void main(String[] args) throws IOException {
	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	StringTokenizer st = new StringTokenizer(br.readLine());
	// 가로
	N = Integer.parseInt(st.nextToken());
	// 세로
	M = Integer.parseInt(st.nextToken());
	
	map = new char[M][N];
	visited  = new boolean[M][N];
	
	// 1. 입력
	for (int i = 0; i < M; i++) {
		String str = br.readLine();
		for (int j = 0; j < N; j++) {
			map[i][j] = str.charAt(j);
		}
	}
	
	int bCount = 0, wCount = 0;
	
	// 2. 모든 지점마다 최대 count 반환 방법 for문
	for (int i = 0; i < M; i++) {		
		for (int j = 0; j < N; j++) {
			// 현재 컬러 
			cur_color = map[i][j];
			sum = 0;
			dfs(i, j); // (y,x)
			if(cur_color=='B') bCount+= (sum*sum);
			else wCount+=(sum*sum);
		}
	}
		System.out.println(wCount + " " + bCount);
}
	private static void dfs(int y, int x) {
		
		
		// 1) 종료 조건 : 이미 방문 했던 곳이나 현재 컬러가 다음 컬러랑 다르면 종료
		if(visited[y][x] == true ||cur_color != map[y][x]) return;
		
		// 2. 로직 : 색깔이 같다면 방문 체크
		visited[y][x] = true;
		sum++;
	
		// (map이니깐 여기서 경계값 체크하기-> 넘어가도 되는지) 
		// 4방탐색	
		if(y < M-1) dfs(y+1, x); // 아래
		if(x < N-1) dfs(y, x+1); // 오른쪽
		if(x > 0) dfs(y, x-1); //왼쪽
		if(y > 0) dfs(y-1, x); // 위
	}
}