[알고리즘] BFS 너비우선탐색

풀이방법 

1. 시작하는 칸을 큐에 넣고 방문했다는 표시를 남김

2. 큐에서 값을 꺼내고 그 칸의 상하좌우로 인접한 칸에 대해 3번을 진행한다.

3. 해당 칸을 이전에 방문햇다면 아무것도 하지않고, 처음으로 방문햇다면 방문했다는 표시를 남기고 해당칸을 큐에 삽입

4. 큐가 빌 때까지 2번을 반복한다.

 -> 모든 칸이 큐에 1번씩 들어가므로 이때의 시간복잡도는 칸이 N개 일때 O(N).

 -> 만약 행이 r개 이고 열이 c개이면 O(rc).

 

(+)시간복잡도 관련 게시글

https://22chaechae.tistory.com/7

[알고리즘] 빅오표기법(Big-O Notation), 시간복잡도, 공간복잡도

 

직접구현하는 것도 좋지만 BFS는 어느정도 정석적인 구현을 가지고 있으므로, 코드를 외워서 푸는 것이 효율적이다.

일반적으로 Queue를 사용한다.

int [] dx = {1,0,-1,0};
int [] dy = {0,1,0,-1}; //상,하,좌,우 로 이동하기

//Queue 사용
Queue ~~(); 

while(!que.isEmpty()){
 인접해있고 && 방문하지않았다면
 
}

 

실수조심

1. 시작점에 방문표시 확인

2. 큐에 넣을 때 방문했다는 표시하기(큐에서 뺄 때하면 큐에 여러번 들어가게 되어 시간초과나 메모리초과 발생)

3. 이웃한 원소가 범위를 벗어났는지에 대한 루틴 있는지 확인

 

 

 

관련 문제 : 기본편 - 백준 1926번 그림

https://www.acmicpc.net/problem/1926

1926번: 그림

public class BOJ1926 {

    static Queue<Nodddee> que;
    static int[] dx = {-1,1,0,0};
    static int[] dy = {0,0,-1,1};
    static int[][] board;
    static boolean[][] visited;
    static int m;
    static int n;
    static int drawmax = 0;//그림최대값
    static int drawcnt = 0;//그림개수


    public static void main(String[] args) throws IOException {
        Scanner scan = new Scanner(System.in);
        n = scan.nextInt();//세로
        m = scan.nextInt();//가로
        board = new int[n][m];
        visited = new boolean[n][m];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                board[i][j] = scan.nextInt();
            }
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (board[i][j] == 1 && !visited[i][j]) {
                    bfs(i, j);
                }
            }
        }
        System.out.println(drawcnt);
        System.out.println(drawmax);
    }//main

    public static void bfs(int x, int y) {
        que = new LinkedList<>();
        que.add(new Nodddee(x, y));
        visited[x][y] = true;
        int count = 0;
        while (!que.isEmpty()) {
            Nodddee nodddee = que.poll();
            count++;
            for (int i = 0; i < 4; i++) {
                int nx = nodddee.x + dx[i];
                int ny = nodddee.y + dy[i];
                if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
                if (visited[nx][ny] || board[nx][ny] == 0) continue;
                visited[nx][ny] = true;
                que.add(new Nodddee(nx, ny));
            }
        }//while

        drawcnt++;
        drawmax = Math.max(drawmax, count);
    }
}

class Nodddee{
    int x;
    int y;

    public Nodddee(int x, int y) {
        super();
        this.x = x;
        this.y = y;
    }
}

맨 처음 큐에 넣는 값을 방문처리 안해서 꽤나 고생했다.