[백준/JAVA] 1303번: 전쟁 - 전투
🔺 문제
1303번: 전쟁 - 전투
첫째 줄에는 전쟁터의 가로 크기 N, 세로 크기 M(1 ≤ N, M ≤ 100)이 주어진다. 그 다음 두 번째 줄에서 M+1번째 줄에는 각각 (X, Y)에 있는 병사들의 옷색이 띄어쓰기 없이 주어진다. 모든 자리에는
www.acmicpc.net
🔺 코드
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
|
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);
}
}
|
cs |
✅ 해결 아이디어
✔ DFS & BFS
💥 유의사항
• 입력받는 n이 세로이고, m이 가로 !
• 탐색 순서를 보면 아래처럼 진행된다.
🔺 다른 풀이들
- BFS 활용한 풀이도 있음
[Java] 백준 1303번 [전쟁 전투] 자바
[Java] 백준 1303번 [전쟁_전투] 자바
velog.io
- i를 가로, j를 세로로 받으려면 이렇게. 그리고 cnt++하는 부분도 약간 다름
백준 1303번: 전쟁 - 전투 [DFS][BFS][Java]
www.acmicpc.net/problem/1303 1303번: 전쟁 - 전투 첫째 줄에는 전쟁터의 가로 크기 N, 세로 크기 M(1 ≤ N, M ≤ 100)이 주어진다. 그 다음 두 번째 줄에서 M+1번째 줄에는 각각 (X, Y)에 있는 병사들의 옷색이 띄
cceeun.tistory.com
- 악... 주석 설명 굿...ㅠㅠㅠ 감사합니다
백준 1303 : 전투 DFS BFS 풀이
https://www.acmicpc.net/problem/1303 1303번: 전쟁 - 전투 첫째 줄에는 전쟁터의 가로 크기 N, 세로 크기 M(1 ≤ N, M ≤ 100)이 주어진다. 그 다음 두 번째 줄에서 M+1번째 줄에는 각각 (X, Y)에 있는 병사들의 옷
terianp.tistory.com
💬 느낀 점
나는 DFS를 참 못한다.. 전쟁 참패...ㅋㅋㅋㅋ
| 1회독 | 2회독 | 3회독 | 4회독 | 5회독 |
| V |
(참고)
[Java] 백준 1303번 [전쟁 전투] 자바
[Java] 백준 1303번 [전쟁_전투] 자바
velog.io