[do it 알고리즘] 백준 2178 (BFS)

문제 설명

 

풀기 전 생각

• DFS와 마찬가지로 다소 나에게 어려워 아이디어만 생각
• 미로니깐 2차원 배열의 map 필요
• 미로와 같은 크기로 2차원 배열의 visited 필요
• 상하좌우는 어떻게 하지..
• BFS는 당연히 '큐' 자료구조를 사용
• 배열에 넘지 않는 선에서 반복하며 map을 지나가기
• 칸 수는 어떻게 기록할까?..

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Baek2178 {
    static int[] dx = {0,1,0,-1}; // 상 하 좌 우
    static int[] dy = {1,0,-1,0};
    static boolean[][] visited; // 방문 여부
    static int[][] Arr; // 맵 
    static int N,M; // 행 렬 사이즈

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        Arr = new int[N][M];
        visited = new boolean[N][M];

        for(int i=0; i<N; i++){
            st = new StringTokenizer(br.readLine());
            String line = st.nextToken();
            for(int j=0; j<M; j++){
                Arr[i][j] = Integer.parseInt(line.substring(j,j+1)); 
                // token은 공백만 구분하기때문에 공백이 없으면 substring으로 잘라 넣기 
            }
        }
        BFS(0,0);
        System.out.println(Arr[N-1][M-1]); // map에 카운트했으므로
    }
    public static void BFS(int i, int j){
        Queue<int[]> queue = new LinkedList<>(); // 한 쌍을 넣기 위해 배열형 큐
        queue.offer(new int[] {i,j}); // 시작점 넣기
        visited[i][j] = true; // 방문 표시

        while(!queue.isEmpty()){ 
            int now[] = queue.poll(); // 꺼내기
            for(int k = 0; k < 4; k++){ // 상 하 좌 우 검색
                int x = now[0] + dx[k]; // now[0] = 현재의 x값
                int y = now[1] + dy[k]; // now[1] = 현재의 y값
                if(x >= 0 && y >= 0 && x < N && y < M){ // 배열을 넘어가면 안됨
                    if(Arr[x][y] !=0 && !visited[x][y]){ // 0이 아닐때 && 방문한 곳이 아닐 때
                        visited[x][y] = true; // 방문 표시
                        Arr[x][y] = Arr[now[0]][now[1]] + 1; // 핵심 : map 배열 위에 다가 이동 칸 카운팅
                                                            // 시작점은 무조건 1이다. 
                        queue.add(new int[] {x,y}); // 큐에다가 넣어주기
                    }
                }
            }
        }

    }
}

새로 알게 된 점

• (상 하 좌 우) 표현 방법
• map 배열 위에다가 카운팅을 넣어 이동 칸 수 세기
• 배열형 큐 자료구조가 가능하다는 점
• substring을 사용한 split방법

스스로 작성해 본 코드

import java.util.*;
import java.io.*;
public class Baek2178{
    static boolean[][] visited;
    static int[][] map;
    static int N,M;
    static int[] dx= {1,0,-1,0};
    static int[] dy= {0,1,0,-1};
    static int[][] count;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        map = new int[N][M];
        visited = new boolean[N][M];

        for(int i = 0 ; i < N; i++){
            String line = br.readLine();
            for(int j = 0 ; j < M; j++){
                map[i][j] = Integer.parseInt(line.substring(j,j+1));
            }
        }
        BFS(0,0);
        System.out.println(map[N-1][M-1]);
    }
    public static void BFS(int i,int j){
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[] {i,j});
        visited[i][j] = true;

        while(!queue.isEmpty()){
            int now[] = queue.poll();
            for(int k =0; k < 4; k++){
                int x = now[0] + dx[k];
                int y = now[1] + dy[k];
                if(x>=0 && y>=0 && x < N && y < M){
                    if(map[x][y] != 0 && !visited[x][y]){
                        queue.offer(new int[] {x,y});
                        count[x][y] = count[now[0]][now[1]] + 1;
                        visited[x][y] = true;
                    }
                }
            }
        }
    }
}

오류 및 개선

• count 배열의 NullPointerException 오류가 발생.
• count라는 배열이 따로 있는 것이 아니라 map위에 카운팅 한다는 핵심을 잊은 것이다...

최종 코드

import java.util.*;
import java.io.*;
public class Baek2178{
    static boolean[][] visited;
    static int[][] map;
    static int N,M;
    static int[] dx= {1,0,-1,0};
    static int[] dy= {0,1,0,-1};
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        map = new int[N][M];
        visited = new boolean[N][M];

        for(int i = 0 ; i < N; i++){
            String line = br.readLine();
            for(int j = 0 ; j < M; j++){
                map[i][j] = Integer.parseInt(line.substring(j,j+1));
            }
        }
        BFS(0,0);
        System.out.println(map[N-1][M-1]);
    }
    public static void BFS(int i,int j){
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[] {i,j});
        visited[i][j] = true;

        while(!queue.isEmpty()){
            int now[] = queue.poll();
            for(int k =0; k < 4; k++){
                int x = now[0] + dx[k];
                int y = now[1] + dy[k];
                if(x>=0 && y>=0 && x < N && y < M){
                    if(map[x][y] != 0 && !visited[x][y]){
                        queue.offer(new int[] {x,y});
                        map[x][y] = map[now[0]][now[1]] + 1;
                        visited[x][y] = true;
                    }
                }
            }
        }
    }
}

DFS, BFS는 단골 문제니 외워서라도 꼭 기억하자!!