[백준] 1012번 '유기농 배추' - Java

문제

---

풀이

1. BFS 이용 (큐 이용)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
	
	static int n, m, k;
	// 상 하 좌 우
	static int[] dx = {-1, 1, 0, 0};
	static int[] dy = {0, 0, -1, 1};
	
	static int[][] matrix;
	static boolean[][] visited;
	
	static class Node {
		int x, y;
		public Node(int x, int y) {
			this.x = x;
			this.y =y;
		}
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int t = Integer.valueOf(br.readLine());
		
		while(t>0) {
			StringTokenizer st = new StringTokenizer(br.readLine(), " ");
			n =Integer.valueOf(st.nextToken());
			m =Integer.valueOf(st.nextToken());
			k =Integer.valueOf(st.nextToken());
			
			matrix = new int[n][m];
			for(int i=0; i<k; i++) {
				st = new StringTokenizer(br.readLine(), " ");
				int r=Integer.valueOf(st.nextToken());
				int c=Integer.valueOf(st.nextToken());
				
				matrix[r][c] = 1;
			}
			visited= new boolean[n][m];
			int ans=0;
			for(int i=0;i<n;i++) {
				for(int j=0;j<m; j++) {
					if(!visited[i][j] && matrix[i][j] == 1) {
						solution(i, j);
						ans ++;
					}
				}
			}
			System.out.println(ans);
			
			t--;
		}
	}
	
	public static void solution(int row, int col){
		Queue<Node> q = new LinkedList<>();
		q.offer(new Node(row, col));
		
		while(!q.isEmpty()) {
			Node cur=q.poll();
			if(visited[cur.x][cur.y]) continue;
			visited[cur.x][cur.y] = true;
			
			for(int i=0; i<4; i++) {
				int next_x = cur.x+dx[i];
				if(next_x <0 || next_x>=n) continue;
				int next_y = cur.y+dy[i];
				if(next_y<0|| next_y>=m) continue;
				
				if(!visited[next_x][next_y]&& matrix[next_x][next_y] == 1) {
					q.offer(new Node(next_x, next_y));
				}
			}
		}
	}
}

 

2. DFS 이용 (Stack 이용)

main 함수에서 solution자리를 dfs 로만 바꾸어주면 됩니다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;
import java.util.StringTokenizer;

public class Main {
	
	static int n, m, k;
	// 상 하 좌 우
	static int[] dx = {-1, 1, 0, 0};
	static int[] dy = {0, 0, -1, 1};
	
	static int[][] matrix;
	static boolean[][] visited;
	
	static class Node {
		int x, y;
		public Node(int x, int y) {
			this.x = x;
			this.y =y;
		}
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int t = Integer.valueOf(br.readLine());
		
		while(t>0) {
			StringTokenizer st = new StringTokenizer(br.readLine(), " ");
			n =Integer.valueOf(st.nextToken());
			m =Integer.valueOf(st.nextToken());
			k =Integer.valueOf(st.nextToken());
			
			matrix = new int[n][m];
			for(int i=0; i<k; i++) {
				st = new StringTokenizer(br.readLine(), " ");
				int r=Integer.valueOf(st.nextToken());
				int c=Integer.valueOf(st.nextToken());
				
				matrix[r][c] = 1;
			}
			visited= new boolean[n][m];
			int ans=0;
			for(int i=0;i<n;i++) {
				for(int j=0;j<m; j++) {
					if(!visited[i][j] && matrix[i][j] == 1) {
						dfs(i, j);
						ans ++;
					}
				}
			}
			System.out.println(ans);
			
			t--;
		}
	}
	
	public static void dfs(int row, int col) {
		Stack<Node> s = new Stack<>();
		s.push(new Node(row, col));
		
		while(!s.isEmpty()) {
			Node cur=s.pop();
			if(visited[cur.x][cur.y]) continue;
			visited[cur.x][cur.y] = true;
			
			for(int i=0; i<4; i++) {
				int next_x = cur.x+dx[i];
				if(next_x <0 || next_x>=n) continue;
				int next_y = cur.y+dy[i];
				if(next_y<0|| next_y>=m) continue;
				
				if(!visited[next_x][next_y]&& matrix[next_x][next_y] == 1) {
					s.push(new Node(next_x, next_y));
				}
			}
		}
	}
}

 

3. DFS 이용 (재귀함수 이용)

위와 마찬가지로 solution 함수가 들어가는 자리에 dfs함수로만 바꿔주면 되고, 재귀함수라서 Node 클래스는 사용할 필요 없습니다.

public static void dfs(int row, int col) {
		if(visited[row][col]) return;
		visited[row][col] = true;
		
		for(int i=0; i<4; i++) {
			int next_x = row+dx[i];
			if(next_x <0 || next_x>=n) continue;
			int next_y = col+dy[i];
			if(next_y<0|| next_y>=m) continue;
			
			if(!visited[next_x][next_y]&& matrix[next_x][next_y] == 1) {
				dfs(next_x, next_y);
			}
		}
	}

---

회고

간단하게 풀렸지만 메모리 초과 때문에 고생 좀 했습니다.

 

아래 링크를 본 뒤에 중복되는 탐색이 있다는 것을 알고 큐(스택)에서 값을 꺼냈을 때 바로 if 문으로 visited 검사를 했더니 통과했습니다.

 

https://www.acmicpc.net/board/view/12905

 

BFS/DFS 오랜만에 ? 푸니까 좋네요.. ㅋㅋ

DFS는 BFS에서 queue를 stack으로만 바꾸어주면 되고, 재귀함수는 조금만 변경해도 되니 한 코드로 세개의 풀이를 도출한다? 가성비 짱 문제였습니다.

다만 좀 빨리 푸는 연습을 해야할 것 같네요