[백준 JAVA] 1303번: 전쟁 - 전투

https://www.acmicpc.net/problem/1303

 

public static int N, M;
public static int[][] map, visited; 
public static List<Integer>;

// 1. N, M 입력
// 1-1. map[M][N], visited[M][N];
// 2. W,B 리스트 만들기
// 3. dfs 탐색
// 4. 출력

 

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

public class Main {
	public static int N, M, cnt, w_cnt = 0, b_cnt = 0;
	public static int[][] visited;
	public static char[][] map;
	public static List<Integer> W, B;
	public static int[] dx = {-1, 0, 1, 0};
	public static int[] dy = {0, 1, 0, -1};

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

		// 1-1. map[M][N], visited[M][N];
		map = new char[M][N];
		visited = new int[M][N];

		for (int i = 0; i < M; i++) {
			String str = br.readLine();
			for (int j = 0; j < N; j++) {
				map[i][j] = str.charAt(j);
			}
		}
		
		// 2. W,B 리스트 만들기
		W = new ArrayList<>();
		B = new ArrayList<>();
		
		// 3. dfs 탐색
		for (int i = 0; i < M; i++) {
			for (int j = 0; j < N; j++) {
				if(visited[i][j] == 0) {
					if(map[i][j] == 'W') {
						cnt = 1;
						visited[i][j] = 1;
						dfs(i, j, 'W');
						W.add(cnt);
						cnt = 0;
					} else if(map[i][j] == 'B') {
						cnt = 1;
						visited[i][j] = 1;
						dfs(i, j, 'B');
						B.add(cnt);
						cnt = 0;
					}
				}
			}
		}
		
		// n^2 계산
		for (int d : W) {
			w_cnt += d * d;
		}
		
		for (int d : B) {
			b_cnt += d * d;
		}
		
		
		// 4. 출력
		System.out.println(w_cnt + " " + b_cnt);

	}
	
	public static void dfs(int x, int y, char c){
		for(int i =0;i<4;i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			
			if(nx < 0 || nx >= M || ny < 0 || ny >=N) continue;
			
			if(visited[nx][ny] == 0) {
				if(map[nx][ny] == c) {
					cnt++;
					visited[nx][ny] = 1;
					dfs(nx, ny, c);
				}
			}
		}
	}
}

 

 

풀이 사항
풀이 일자: 2024.08.20
풀이 시간: 30분
채점 결과: 정답
예상 문제 유형: DFS

풀이 방법
단지 번호 붙이기랑 똑같이 풀이했음

cnt초기화, dfs탐색, 리스트에 cnt 넣어주기

깔끔하지 못했던 풀이는 반성

1. 모여있는 군사의 수를 입력받는 리스트를 굳이 dfs에 넣어주지 않아도 되지만 처음엔 파라미터로 넣어주었다가 뺏다.
   -> 언제 계산할지를 잘 생각해서 메서드를 구성하자
2. 처음 탐색할 경우 dfs에 들어가기 전에 visited[i][j]를 빼먹었었다.
   -> 방문 배열 확인은 기본적이라 생각한다. 언제 초기화해주는지 첫번째 들어갈땐 어떻게 초기화할것인지 항상 고민하자.
3. 유효한 값임을 확인하는 if문에 왜 break를 썻는지 이해가 안된다. if(nx < 0 || nx >= M || ny < 0 || ny >=N) break;
   -> continue이다. 이거땜에 10분썼다. 그래도 빨리 찾아낸 편이라 생각한다. 생각하고 코드짜자. 반성하자.