문제 링크
https://www.acmicpc.net/problem/1926
나의 기록
✅ 알고리즘 분류 : BFS
✅ 성공 여부 : ✔
✅ 문제 난이도 : 실버1
✅ 체감 난이도 : Easy
접근 방법
무난한 4방탐색 문제였다. map[i][j]의 값을 0으로 만드는 방법으로 방문 체크를 할 수 있다는 것을 기억하자.
코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class bj1926_그림 {
static int[] di = {-1,1,0,0};
static int[] dj = {0,0,-1,1};
static int N, M; // 세로, 가로 크기
static int cnt, max, size; // 그림의 개수, 가장 넓은 그림의 넓이, 하나 그림의 넓이
static int[][] map;
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());
cnt = 0; max = 0;
map = new int[N][M];
for(int i = 0 ; i < N ; i++){
st = new StringTokenizer(br.readLine());
for(int j = 0 ; j < M ; j++){
map[i][j] = Integer.parseInt(st.nextToken());
}
}
// DFS
for(int i = 0 ; i < N ; i++){
for(int j = 0 ; j < M ; j++){
if(map[i][j] == 1) {
cnt++;
size = 0;
dfs(i,j);
max = Math.max(size, max);
}
}
}
// 출력
System.out.println(new StringBuilder().append(cnt).append("\n").append(max).toString());
}
public static void dfs(int x, int y){
map[x][y] = 0; // 방문 처리
size++; // 사이즈 + 1
// 4방 탐색
for(int d = 0 ; d < 4 ; d++){
int nx = x + di[d];
int ny = y + dj[d];
if(isValid(nx,ny)){
dfs(nx, ny);
}
}
}
public static boolean isValid(int x, int y){
return x >= 0 && x < N && y >= 0 && y < M && map[x][y] == 1;
}
}
'알고리즘 (Java)' 카테고리의 다른 글
(Java) 백준 20164 홀수 홀릭 호석 (0) | 2023.05.09 |
---|---|
(Java) 백준 4358 생태학 (0) | 2023.04.26 |
(Java) 백준 2075 N번째 큰 수 (0) | 2023.04.26 |
(Java) 백준 9095 1, 2, 3 더하기 (0) | 2023.04.14 |
(Java) 백준 11725 트리의 부모 찾기 (0) | 2023.04.14 |