반응형
-내 생각
DFS, BFS 분류가 되어있는 유기농 배추 문제이다. 문제 자체는 백준 2667 단지 번호 붙이기와 다르게 보이지만, 사실상 같은 문제라고 생각했다. 단지 번호 붙이기 같은 경우에는 인접한 아파트의 수를 카운트하는 것이라면, 이 문제는 인접한 배추의 묶음단위를 카운트하는 것이었다. 그렇기 때문에 DFS를 이용해 깊이를 우선하여 완전 탐색을 실시해 풀 수 있다고 생각했다.
-해법
코드의 내용은 단지번호 붙이기에서 약간만 수정해주면 된다.
import java.util.*;
public class Main {
static int node[][]; // 배추밭 배열
static int check[][]; // 배추방문 배열
static int cnt =0; // 배추의 묶음을 카운트 할 변수
static ArrayList<Integer> array = new ArrayList<>(); // 각 테스트케이스마다의 결과를 저장할 어레이 리스트
static void dfs(int x,int y) { // DFS탐색을 수행 할 메소드
check[x][y] =1; // 방문여부 표시
// 기준점의 동서남북을 확인한다 자세한 코드설명은 단지번호 붙이기를 참고
if( y<node[x].length-1 && node[x][y+1]==1 && check[x][y+1]==0) {
dfs(x,y+1);
}
if(x<node.length-1 && node[x+1][y]==1&& check[x+1][y]==0) {
dfs(x+1,y);
}
if(y>0 && node[x][y-1]==1&& check[x][y-1]==0) {
dfs(x,y-1);
}
if(x>0 && node[x-1][y]==1&& check[x-1][y]==0) {
dfs(x-1,y);
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int t= sc.nextInt(); // 테스트 케이스
for(int i=0;i<t;i++) {
int m = sc.nextInt(); // 배추밭 가로길이
int n = sc.nextInt(); // 배추밭 세로길이
int k = sc.nextInt(); // 배추 개수
node = new int[n][m];
check = new int[n][m];
cnt=0;
for(int j=0;j<k;j++) { // 배추 위치 입력
int a = sc.nextInt();
int b = sc.nextInt();
node[b][a] = 1;
}
for(int j=0;j<node.length;j++) {
for(int g=0;g<node[j].length;g++) {
if(node[j][g] == 1 && check[j][g]==0) { // 배추가 심어져있고 방문하지 않았던 배추를 인자로 전달
cnt++; // 배추의 묶음마다 cnt증가
dfs(j,g);
}
}
}
array.add(cnt); // 테스트케이스마다 배추의 묶음 수를 저장
}
for(int i=0;i<array.size();i++) { // 출력
System.out.println(array.get(i));
}
}
}단지 번호 붙이기와 같은 유형의 문제이다. 역시 BFS를 이용해 풀어보았다.
import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
class Dot{
int x;
int y;
public Dot(int x, int y) {
super();
this.x = x;
this.y = y;
}
public int getX() {
return x;
}
public void setX(int x) {
this.x = x;
}
public int getY() {
return y;
}
public void setY(int y) {
this.y = y;
}
}
class Main {
static int num = 0;
static int dx[] = {1,-1,0,0};
static int dy[] = {0,0,1,-1};
static void bfs(int[][] a, boolean[][] check, Dot d) {
Queue<Dot> q = new LinkedList<>();
q.offer(d);
check[d.getX()][d.getY()] = true;
while(!q.isEmpty()) {
Dot d_p = q.poll();
int x = d_p.getX();
int y = d_p.getY();
for(int i=0;i<4;i++) {
int nx = x + dx[i];
int ny = y + dy[i];
if(nx>=a.length || nx<0 || ny>=a[nx].length || ny < 0) continue;
if(check[nx][ny]) continue;
if( a[nx][ny] == 1){
check[nx][ny] = true;
q.offer(new Dot(nx,ny));
}
}
}
}
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int t = in.nextInt();
int map[][] ;
boolean check[][];
Dot d;
for(int i = 0; i<t; i++) {
int m =in.nextInt(); // 가로
int n = in.nextInt(); // 세로
int k = in.nextInt(); // 배추 수
map = new int[m][n]; // 배추 밭 생성
check = new boolean[m][n]; // 방문 여부 체크 배열
for(int j = 0;j<k;j++) { // 배추 좌표 입력
map[in.nextInt()][in.nextInt()] = 1;
}
for(int q =0;q<map.length;q++) {
for(int w =0; w<map[q].length;w++) {
if(map[q][w] == 1 && check[q][w] == false) { // 배추가 있고 방문하지 않았다면
d = new Dot(q,w);
bfs(map,check,d); // 해당 좌표부터 BFS 수행
num++; // 수행한 뒤 지렁이 수 증가
}
}
}
System.out.println(num);
num = 0;
}
}
}반응형