🧑🏻‍💻 문제

💡문제 분석 요약

DFS 또는 BFS 를 통해서 인접한 노드를 탐색하며 몇 번 탐색되는지 구하는 문제이다.

💡알고리즘 설계

BFS 를 활용하여 로직을 설계 했다.
1. 시작 점으로부터 상하좌우를 움직이며 '1'이 있는 경우 큐에 위치에 대한 값을 넣어 반복한다.
2. BFS가 시작할 때마다 count를 해주어 개수를 구한다.

좌표에 대한 값을 큐에 넣어줘야 하기에 Point라는 x,y 값을 넣을 수 있는 Class를 만들어 사용했다.

💡코드 (BFS 활용)

public class 백준_1012_유기농배추2 {
	
	static class Point{
		int x;
		int y;
		
		Point(int x, int y) {
			this.x = x;
			this.y = y;
		}
	}
	
	static boolean[][] visited;
	static Queue<Point> q;
	static int[] dx = {1, 0, -1, 0};
	static int[] dy = {0, 1, 0, -1};
	static int N;
	static int M;
	static int count;
	static int[][] arr;
	
	private static void BFS(int a, int b) {
		count++;
		visited[a][b] = true;
		q.add(new Point(a,b));
		
		while(!q.isEmpty()){
			Point p = q.poll();
			for (int i = 0; i < 4; i++) {
				int newA = p.x + dx[i];
				int newB = p.y + dy[i];
				
				if (newA >= 0 && newA < N && newB >= 0 && newB < M) {
					if (arr[newA][newB] == 1 && !visited[newA][newB]) {
						q.add(new Point(newA, newB));
						visited[newA][newB] = true;
					}
				}
			}
		}
	}
	
	public static void main(String[] args) throws IOException {
		StringBuilder sb = new StringBuilder();
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(br.readLine());
		
		while (T-- > 0) {
			count = 0;
			StringTokenizer st = new StringTokenizer(br.readLine());
			M = Integer.parseInt(st.nextToken());
			N = Integer.parseInt(st.nextToken());
			int K = Integer.parseInt(st.nextToken());
			
			arr = new int[N][M];
			visited = new boolean[N][M];
			for (int i = 0; i < K; i++) {
				st = new StringTokenizer(br.readLine());
				int a = Integer.parseInt(st.nextToken());
				int b = Integer.parseInt(st.nextToken());
				
				arr[b][a] = 1; 
			}
			q = new LinkedList<Point>();
			for (int i = 0 ; i < N; i++) {
				for (int j = 0 ;j < M; j++) {
					if (arr[i][j] == 1 && !visited[i][j]) {
						BFS(i,j);
					}
				}
			}
			sb.append(count).append("\n");
		}
		System.out.println(sb);
	}

}

💡시간복잡도

최악의 경우 BFS는 모든 배추밭의 칸을 한 번씩 방문하게 되므로,
BFS의 시간 복잡도는 𝑂(𝑁×𝑀)

💡 틀린 이유

처음에 BFS 를 활용하려 할 때 어떻게 좌표 값 (2차원 배열의 인덱스)를 큐에 담을지 고민됐다. 결국엔 Class를 생성하여 클래스의 인스턴스를 큐에 넣는 방식으로 해결했다.

💡 다른 풀이 (DFS)

public class 백준_1012_유기농배추 {
	static final int MAX = 60;
	static boolean[][] graph;
	static boolean[][] visited;
	static int[] dx = {1, -1, 0, 0};
	static int[] dy = {0, 0, 1, -1};
	
	private static void dfs(int x, int y) {
		visited[x][y] = true;
		for (int i = 0; i < 4; i++) {
			int newX = x + dx[i];
			int newY = y + dy[i];
			if (graph[newX][newY] && !visited[newX][newY]) {
				dfs(newX, newY);
			}
		}
	}

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(br.readLine());
		
		while (T-- > 0) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			int M = Integer.parseInt(st.nextToken());
			int N = Integer.parseInt(st.nextToken());
			int K = Integer.parseInt(st.nextToken());
			
			graph = new boolean[MAX][MAX];
			visited = new boolean[MAX][MAX];
			
			// 그래프 정보 입력
			for (int i = 0; i < K; i ++) {
				st = new StringTokenizer(br.readLine());
				int x = Integer.parseInt(st.nextToken());
				int y = Integer.parseInt(st.nextToken());
				
				graph[y+1][x+1] = true;
				
			}
			
			int answer = 0;
			for (int i = 1; i < N+1; i++) {
				for (int j = 1; j < M+1; j++) {
					if (graph[i][j] && !visited[i][j]) {
						dfs(i, j);
						answer += 1;
					}
				}
			}
			System.out.println(answer);
		}
	}

}

💡 느낀점 or 기억할정보

BFS 에 좌표 값을 저장할 때 Class 활용하기!