BOJ_1012_유기농 배추
2021. 12. 15. 10:05ㆍ백준 알고리즘(BOJ)
1
구분: 그래프 이론, 그래프 탐색, DFS, BFS
언어: Java
전략
- 배추의 인접한 부분을 묶어, 전체 덩어리의 개수를 구한다
- 배추가 있다면 그 부분을 깊이 우선 탐색을 통해 인접한 배추들을 구한다
- 이미 방문한 배추는 또 방문하지 않는다
2. 코드
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
public class Main {
static int X, Y;
static boolean[][] visit; //지렁이 방문 여부를 나타냄
static int[][] map; //배추 밭
//좌표를 담을 class생성
static class Node{
int y, x;
Node(int y, int x){
this.y = y;
this.x = x;
}
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int T = scanner.nextInt();
for(int tc = 1; tc<=T; tc++) {
X = scanner.nextInt();
Y = scanner.nextInt();
visit = new boolean[Y][X];
map = new int[Y][X];
int op = scanner.nextInt();
//각 위치에 배추 심어 - 1이 배추
for(int i = 0; i<op; i++) {
int xx = scanner.nextInt();
int yy = scanner.nextInt();
map[yy][xx] = 1;
}
int ans = 0;//정답, 지렁이 수
for(int i = 0; i<Y; i++) {
for(int j = 0; j<X; j++) {
//배추가 심어져 있고, 방문하지 않았다면
if(map[i][j]==1 && !visit[i][j]) {
//dfs(i,j);
bfs(i,j);
ans++;
}
}
}
System.out.println(ans);
}//test
}//main
static int[] dx = {-1,1,0,0};
static int[] dy = {0,0,-1,1};
//깊이 우선 탐색으로 인접한 배추들을 탐색
private static void dfs(int y, int x) {
//방문 처리
visit[y][x] = true;
//사방 탐색
for(int d = 0; d<4; d++) {
int nx = x + dx[d];
int ny = y + dy[d];
//범위 벗어나면 지나가
if(nx<0||ny<0|| nx>=X|| ny>=Y)
continue;
//이미 방문했거나 배추가 아니라면 지나가
if(visit[ny][nx] || map[ny][nx]!=1)
continue;
dfs(ny,nx);
}
}
//너비 우선 탐색을 한 경우
private static void bfs(int y, int x) {
Queue<Node> q = new LinkedList();
//큐에 넣고 방문처리
q.add(new Node(y, x));
visit[y][x] = true;
while(!q.isEmpty()) {
Node node = q.poll();
int qx = node.x;
int qy = node.y;
for(int d = 0; d<4; d++) {
int nx = qx + dx[d];
int ny = qy + dy[d];
//범위 벗어나면 지나가
if(nx<0||ny<0||nx>=X||ny>=Y)
continue;
//방문이미 했거나 배추가 아니면 지나가
if(visit[ny][nx] || map[ny][nx]!=1)
continue;
//새로운 좌표를 큐에 넣고, 방문 처리
q.add(new Node(ny, nx));
visit[ny][nx] = true;
}
}
}
}
3
- 연습하기 정말 좋은 문제인것 같다
- BFS로도 풀어봐야 겠다 -> 코드에 추가
'백준 알고리즘(BOJ)' 카테고리의 다른 글
BOJ_3040_백설 공주와 일곱 난쟁이 (0) | 2022.08.07 |
---|---|
BOJ_11724_연결 요소의 개수 (0) | 2021.12.15 |
BOJ_14620_꽃길 (0) | 2021.12.10 |
BOJ_16439_치킨치킨치킨 (0) | 2021.12.07 |
BOJ_15721_번데기 (0) | 2021.12.07 |