BOJ_1012_유기농 배추

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로도 풀어봐야 겠다 -> 코드에 추가