백준 1303번: 전쟁 - 전투 [DFS][BFS][Java]

www.acmicpc.net/problem/1303

1303번: 전쟁 - 전투

 

 

 

* DFS방식

0,0부터 돌면서 방문 안한곳이 나오면 dfs가 끝날때까지 같은 색깔인 아군들의 갯수를 카운트한다.

import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Arrays;
import java.util.Scanner;

public class Main {

	public static Character map[][];
	public static boolean visit[][];
	public static int dy[] = {1, 0, -1, 0};
	public static int dx[] = {0, 1, 0, -1};
	public static int b = 0, w = 0 , N,M,c;
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		M = sc.nextInt();
		N = sc.nextInt();
		map = new Character[N][M];
		visit = new boolean[N][M];
        
		for(int i =0;i<N;i++) {
			String str = sc.next();
			for(int j=0;j<M;j++) {
                char ch = str.charAt(j);
				map[i][j] = ch;//str.charAt(j);
			}
		}
		
		for(int i =0;i<N;i++) {
			for(int j = 0;j<M;j++) {
				if(!visit[i][j]) {
					c=1;
					dfs(map[i][j],i,j);
					
					if(map[i][j]=='W')
						w+=(c*c);
					else
						b+=(c*c);
					
					
				}
			}
		}

		
		System.out.println(w+" "+b);
	}
	public static void dfs(char ch, int row, int col) {
		
		visit[row][col] = true;
//		System.out.println(" "+ch+" ["+row+","+col+"] "+cnt+" "+c);
		
		//이동
		for(int i = 0; i<dx.length;i++) {
			int nx = row + dx[i];
			int ny = col + dy[i];
			
			//배열 범위 벗어나는가?
			if(nx >= N || nx < 0 || ny >= M || ny < 0)
				continue;
			//이미 방문했던 곳인가?
			if(visit[nx][ny])
				continue;
			//ch이 다른 값인가?
			if(map[nx][ny] != ch)
				continue;
			
			c++;
			dfs(ch,nx,ny);
			
		}
		
	}

}

 

 

*BFS방식

동서남북 방향에 같은 문자가 있으면 Queue에 add

Queue가 빌 때까지 반복

import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {

	public static Character map[][];
	public static boolean visit[][];
	public static int dy[] = { 1, 0, -1, 0 };
	public static int dx[] = { 0, 1, 0, -1 };
	public static int b = 0, w = 0, N, M, c = 0;
	public static Queue q = new LinkedList<>();

	public static void main(String[] args) throws FileNotFoundException {
		// TODO Auto-generated method stub

		Scanner sc = new Scanner(System.in);
		M = sc.nextInt();
		N = sc.nextInt();
		sc.nextLine();
		map = new Character[N][M];
		visit = new boolean[N][M];
		for (int i = 0; i < N; i++) {
			String str = sc.nextLine();
			for (int j = 0; j < M; j++) {
				map[i][j] = str.charAt(j);
			}
		}

		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				if (!visit[i][j]) {
					c = 1;
					visit[i][j] = true;
					q.add(new int[] { i, j });

					bfs();
					
					if(map[i][j]=='W')
						w += c*c;
					else
						b += c*c;
				}

			}
		}

		System.out.println(w + " " + b);
	}

	public static void bfs() {

		while (!q.isEmpty()) {
			
			int[] pos = (int[]) q.poll();
			int row = pos[0];
			int col = pos[1];
			
			// 이동
			for (int i = 0; i < dx.length; i++) {
				int nx = row + dx[i];
				int ny = col + dy[i];

				// 배열 범위 벗어나는가?
				if (nx >= N || nx < 0 || ny >= M || ny < 0)
					continue;
				// 이미 방문했던 곳인가?
				if (visit[nx][ny])
					continue;
				// ch이 다른 값인가?
				if (map[nx][ny] != map[row][col])
					continue;

				c++;
				visit[nx][ny] = true;
				q.add(new int[] {nx,ny});

			}
		}

	}

}