알고리즘 스터디 4주차 2

15721

• 알고리즘 : DFS, BFS
• 난이도 :실버2

문제

1012

접근

• 보통 이렇게 그래프 형식이라면 DFS, BFS이다.
• 인접한 배추의 그룹은 지렁이 갯수와 같다.
• 깊이우선과 너비우선 둘다 풀어도 될듯.

가정

• 깊이우선, 너비우선 모두 가능한 문제인거 같다.
• 너비우선으로 풀어본다.
• 전체 그래프를 저장한다.
• 배추의 위치를 저장한다.

풀어보기

package org.example;

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

public class Main {
	// 그래프의 크기와 방문 여부를 저장할 변수들
	private static int[][] graph;
	private static boolean[][] visited;
	private static int rows;
	private static int cols;

	// 이동 방향 (상, 하, 좌, 우)
	private static final int[] dx = {-1, 1, 0, 0};
	private static final int[] dy = {0, 0, -1, 1};

	public static void bfs(int x, int y){
		Queue<int[]> queue = new LinkedList<>();
		queue.offer(new int[]{x, y});
		visited[x][y] = true;

		while(!queue.isEmpty()){
			int[] position = queue.poll();
			int curX = position[0];
			int curY = position[1];

			for(int i = 0; i < dx.length; i++){
				int nextX = curX + dx[i];
				int nextY = curY + dy[i];
				if(returnTrueIfOutOfBound(nextX, nextY)){continue;}
				if(graph[curX][curY] == 0){continue;}
				if(!visited[nextX][nextY]){
					visited[nextX][nextY] = true;
					queue.offer(new int[]{nextX, nextY});
				}
			}
		}
	}
	public static boolean returnTrueIfOutOfBound(int nextX, int nextY){
		if(nextX < 0 ){
			return true;
		}
		if(nextY < 0 ){
			return true;
		}
		if(nextX >= rows) {
			return true;
		}
		return nextY >= cols;
	}
	public static void main(String[] args) throws IOException {
		BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
		int game  = Integer.parseInt(reader.readLine());
		for(int k = 0; k < game; k++){

		String MNK = (reader.readLine());
		String[] arrMNK = MNK.split(" ");

		rows =Integer.parseInt(arrMNK[0]);
		cols = Integer.parseInt(arrMNK[1]);
		int wormCount = Integer.parseInt(arrMNK[2]);
		graph = new int[rows][cols];
		visited = new boolean[rows][cols];

		for(int i = 0; i < rows; i++){
			for(int j = 0; j < cols; j++){
				graph[i][j] = 0;
			}
		}

		for(int i = 0; i < wormCount; i++){
			String[] arrXY = (reader.readLine()).split(" ");
			int x  = Integer.parseInt(arrXY[0]);
			int y  = Integer.parseInt(arrXY[1]);
			graph[x][y] = 1;
		}


		int groupCount = 0;

		for(int i = 0; i < rows; i++){
			for(int j = 0; j < cols; j++){
				if(graph[i][j] == 0){continue;}
				if(visited[i][j]){continue;}
				bfs(i, j);
				groupCount++;
			}
		}
		System.out.println(groupCount);
		}
	}
}

시행착오

참고자료

• 큐 예제코드

import java.util.*;

public class BFSExample {

    // 그래프의 크기와 방문 여부를 저장할 변수들
    private static int[][] graph;
    private static boolean[][] visited;
    private static int rows, cols;

    // 이동 방향 (상, 하, 좌, 우)
    private static final int[] dx = {-1, 1, 0, 0};
    private static final int[] dy = {0, 0, -1, 1};

    // BFS로 연결된 부분을 탐색하여 방문 처리
    private static void bfs(int x, int y) {
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{x, y});
        visited[x][y] = true;

        while (!queue.isEmpty()) {
            int[] pos = queue.poll();
            int currX = pos[0];
            int currY = pos[1];

            // 4가지 방향으로 탐색
            for (int i = 0; i < 4; i++) {
                int nx = currX + dx[i];
                int ny = currY + dy[i];

                // 그래프의 경계를 넘지 않으며, 연결된 노드가 있고, 아직 방문하지 않은 위치일 경우
                if (nx >= 0 && nx < rows && ny >= 0 && ny < cols) {
                    if (graph[nx][ny] == 1 && !visited[nx][ny]) {
                        visited[nx][ny] = true;
                        queue.offer(new int[]{nx, ny});
                    }
                }
            }
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        rows = sc.nextInt(); // 그래프의 행 크기
        cols = sc.nextInt(); // 그래프의 열 크기

        graph = new int[rows][cols];
        visited = new boolean[rows][cols];

        // 그래프 초기화: 1은 연결된 노드, 0은 비어 있는 노드로 간주
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                graph[i][j] = sc.nextInt();
            }
        }

        int groupCount = 0; // 연결된 그룹의 수

        // 그래프의 각 위치를 순회하며 BFS로 군집 찾기
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (graph[i][j] == 1 && !visited[i][j]) {
                    bfs(i, j);
                    groupCount++; // 새로운 군집을 찾을 때마다 카운트 증가
                }
            }
        }

        System.out.println(groupCount); // 총 연결된 군집의 수 출력

        sc.close();
    }
}