알고리즘 문제 풀이 - BFS

BOJ 25418번 정수 a를 k로 만들기
https://www.acmicpc.net/problem/25418

 

 

접근 방법

 

 

풀이 코드

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int A = sc.nextInt();
        int K = sc.nextInt();
        
        Queue<int[]> q = new LinkedList<>();
        boolean[] visited = new boolean[K + 1]; // 이미 방문한 숫자를 추적하기 위한 배열
        q.offer(new int[]{A, 0});
        visited[A] = true;

        while (!q.isEmpty()) {
            int[] current = q.poll();
            int num = current[0];
            int count = current[1];

            if (num == K) {
                System.out.println(count);
                break;
            }

            if (num + 1 <= K && !visited[num + 1]) {
                visited[num + 1] = true;
                q.offer(new int[]{num + 1, count + 1});
            }

            if (num * 2 <= K && !visited[num * 2]) {
                visited[num * 2] = true;
                q.offer(new int[]{num * 2, count + 1});
            }
        } // while문 

    } // main
} // class

 

 

후기

처음에는 이미 방문한 숫자를 추적하기 위한 배열(visited) 없이 진행했는데 3번 테케에서 에러 발생 ,,

BFS에서는 방문한 곳을 체크하는 것이 필수라는 것을 알게 되었다.

 

---

BOJ 2178번 미로 탐색
https://www.acmicpc.net/problem/2178

 

 

접근 방법

'

 

 

풀이 코드

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {
    // 미로를 저장할 배열
    static int[][] arr;
    // 방문 여부 및 이동 횟수를 저장할 배열
    static int[][] check;
    // 방향 배열
    static int[] dx = {0, 0, 1, -1};
    static int[] dy = {1, -1, 0, 0};
    // 미로의 크기
    static int N, M;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        N = sc.nextInt();
        M = sc.nextInt();
        arr = new int[N][M];
        check = new int[N][M];
        
        // 미로 입력 받기
        for (int i = 0; i < N; i++) {
            String line = sc.next();
            for (int j = 0; j < M; j++) {
                arr[i][j] = line.charAt(j) - '0';
            }
        }
        
        System.out.println(bfs(0, 0));
    } // main
    
    public static int bfs(int x, int y) {
        Queue<int[]> que = new LinkedList<>();
        que.add(new int[]{x, y});
        
        check[x][y] = 1;
        
        while (!que.isEmpty()) {
            int[] current = que.poll();
            int cx = current[0];
            int cy = current[1];
            
            // 목적지 도달
            if (cx == N - 1 && cy == M - 1) break;
            
            // 4방향 탐색
            for (int i = 0; i < 4; i++) {
                int nx = cx + dx[i];
                int ny = cy + dy[i];
                
                // 미로 범위 내에 있는지 확인
                if (nx >= 0 && nx < N && ny >= 0 && ny < M) {
                    // 길이고 방문하지 않은 곳이라면
                    if (arr[nx][ny] == 1 && check[nx][ny] == 0) {
                        check[nx][ny] = check[cx][cy] + 1;
                        que.add(new int[]{nx, ny});
                    }
                }
            } // for문 
        } // while문 
        return check[N-1][M-1];
    } // bfs 

} // class

 

 

후기

다른 문제에도 적용 가능한 기본적인 코드라는 것을 느낌.

즉, 활용 가능도 높은 코드라 생각하게 되었다.

 

 

---

BOJ 1926번 그림
https://www.acmicpc.net/problem/1926

 

 

접근 방법

 

 

풀이 코드

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {
	// 그림 저장할 배열
	static int[][] arr;
	// 방문 여부를 저장할 배열
	static boolean[][] check;
	// 방향 배열
	static int[] dx = { 0, 0, 1, -1 };
	static int[] dy = { 1, -1, 0, 0 };
	// 그림의 크기
	static int N, M;

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

		N = sc.nextInt();
		M = sc.nextInt();
		arr = new int[N][M];
		check = new boolean[N][M];

		// 그림 입력 받기
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				arr[i][j] = sc.nextInt();
			}
		}

		int numPictures = 0; // 총 그림의 수
		int maxSize = 0; // 가장 큰 그림의 크기

		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				if (arr[i][j] == 1 && !check[i][j]) {
					numPictures++;
					int size = bfs(i, j);
					if (size > maxSize) {
						maxSize = size;
					}
				}
			}
		}

		System.out.println(numPictures);
		System.out.println(maxSize);
	} // main

	public static int bfs(int x, int y) {
		Queue<int[]> que = new LinkedList<>();
		que.add(new int[] { x, y });

		check[x][y] = true;
		int size = 1; // 현재 그림의 크기

		while (!que.isEmpty()) {
			int[] current = que.poll();
			int cx = current[0];
			int cy = current[1];

			// 4방향 탐색
			for (int i = 0; i < 4; i++) {
				int nx = cx + dx[i];
				int ny = cy + dy[i];

				// 범위 내에 있는지 확인
				if (nx >= 0 && nx < N && ny >= 0 && ny < M) {
					// 그림이고 방문하지 않은 곳이라면
					if (arr[nx][ny] == 1 && !check[nx][ny]) {
						check[nx][ny] = true;
						que.add(new int[] { nx, ny });
						size++;
					}
				}
			}
		}
		return size;
	} // bfs

} // class

 

 

후기

bfs를 어떻게 구현해야 하는지 처음엔 감이 잘 안 잡혔었다.

for 문을 돌면서 시작점을 변경해 bfs 돌리는 방식을 깨닫고 그 뒤로는 나름 잘 풀린 듯한?

이전 문제와 유사하다고 느낀 문제 중 하나

 

---