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

🔺 문제

1303번: 전쟁 - 전투

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    static int N, M;    // 가로 세로
    static int nowX;
    static int nowY;
    static int cnt = 0;
    
    static int wCnt = 0;
    static int bCnt = 0;
    static char [][] map;
    static boolean[][] visited;
    
    static int[] dx = {0, 0, -1, 1};  // 좌우
    static int[] dy = {-1, 1, 0, 0};  // 상하
    
    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());   // 열 = col = 가로 크기 = x
        M = Integer.parseInt(st.nextToken());   // 행 = row = 세로 크기 = y
        
        // 지도 생성
        map = new char[M][N]; // [row][col] => y, x
        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 이용해 탐색
        visited = new boolean[M][N];
        for(int i = 0 ; i < M ; i++) {      // 세로 = row = y
            for(int j = 0 ; j < N ; j++) {  // 가로 = col = x
                if(!visited[i][j]) {
                    char color = map[i][j];
                    cnt = 0;
                    DFS(j, i, color);
                    
                    if(color == 'W') wCnt += cnt * cnt;
                    else             bCnt += cnt * cnt;
                }
            }
        }
 
        System.out.println(wCnt + " " + bCnt);
    }
    
    // DFS
    static void DFS(int x, int y, char color) {
        visited[y][x] = true;
        cnt++;
        
        for(int i = 0 ; i < 4 ; i++) {
            nowX = x + dx[i];
            nowY = y + dy[i];
            
            if(rangeChk() == true && (map[nowY][nowX] == color) && !visited[nowY][nowX]) {
                DFS(nowX, nowY, map[nowY][nowX]);
            }
        }
    }
    
    static boolean rangeChk() {
        return (0 <= nowY && nowY < M && 0 <= nowX && nowX < N);
    }
}

✅ 해결 아이디어
✔ DFS  & BFS

 

💥 유의사항

• 입력받는 n이 세로이고,  m이 가로 !

• 탐색 순서를 보면 아래처럼 진행된다.

 

---

🔺 다른 풀이들

- BFS 활용한 풀이도 있음

[Java] 백준 1303번 [전쟁 전투] 자바

 

 

- i를 가로, j를 세로로 받으려면 이렇게. 그리고 cnt++하는 부분도 약간 다름

 

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

 

 

- 악... 주석 설명 굿...ㅠㅠㅠ 감사합니다

백준 1303 : 전투 DFS BFS 풀이

---

💬 느낀 점

나는 DFS를 참 못한다.. 전쟁 참패...ㅋㅋㅋㅋ

 

 

1회독	2회독	3회독	4회독	5회독
V

---

(참고)

[Java] 백준 1303번 [전쟁 전투] 자바