[백준] code.plus(BFS 알고리즘,JAVA)16946번, 벽 부수고 이동하기 4

문제 링크

16946번: 벽 부수고 이동하기 4

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

 

접근 방법

그래프 알고리즘이란?

각 정점과 연결하는 선분의 정보를 가지고 BFS(너비 우선 탐색), DFS(깊이 우선 탐색) .... 등을 이용하여 정점에서 다른 정점으로 가는 최소값, 최대값 등의 문제에서 출력하라는 결과를 구하는 알고리즘입니다.

 

BFS?

BFS(너비 우선 탐색)은 아래 그림처럼 시작 노드에 인접한 노드를 모두 탐색한 후 인접한 노드를 기준으로 다시 인접한 노드를 찾아내는 것을 반복하여 탐색합니다.

시작 노드 탐색이 끝나면 인접했던 노드를 시작 노드로 생각하고 다시 탐색합니다.

출처: https://ko.wikipedia.org/wiki/%EB%84%88%EB%B9%84_%EC%9A%B0%EC%84%A0_%ED%83%90%EC%83%89

더 자세한 내용은 아래 링크에 들어가서 확인해주시면 감사하겠습니다.

너비 우선 탐색 - 위키백과, 우리 모두의 백과사전

 

이 문제에 핵심은

1. 맵에서 이동할 수 있는 구간 0, 벽이 있는 구간 1로 주어집니다.

2. 벽을 부술 수 있으며 모든 구간을 탐색하여 벽이 부서지는 횟수를 누적하여 맵을 결과로 출력한다.

3. 벽인 곳은 마지막에 10의 나머지로 결과를 출력한다.

 

모든 0인 구역으로 BFS 탐색을 진행하여 벽을 만나면 +1을 하는 방법으로 진행하였으나 "시간 초과"가 발생하였습니다.

 

시간 복잡도를 살펴보니 N² * M²로 진행되어 시간초과가 발생한다고 깨닫게 되었습니다.

 

그래서 0인 구역을 그룹으로 만들어서 해당 그룹과 인접하면 해당 그룹의 0의 개수를 더하였습니다.

 

예제입력 2.

1	1	0	0	1
0	0	1	1	1
0	1	0	1	0
1	0	1	0	1

0인 구역들을 그룹으로 나누면

1	1	0	0	1
0	0	1	1	1
0	1	0	1	0
1	0	1	0	1

그룹 1 : 2

그룹 2 : 3

그룹 3 : 1

그룹 4 : 1

그룹 5 : 1

그룹 6 : 1

 

벽에 인접한 그룹을 탐색합니다.

1	1	0	0	1
0	0	1	1	1
0	1	0	1	0
1	0	1	0	1

(0,0)의 인접한 그룹 : 그룹 2

= 3

 

(0,1)의 인접한 그룹 : 그룹1, 그룹2

= 2 + 3 = 5

 

(0,4)의 인접한 그룹 : 그룹1

= 2

 

(1,2)의 인접한 그룹 : 그룹1, 그룹2, 그룹3

= 2 + 3 + 1 = 6

 

(1,3)의 인접한 그룹 : 그룹1

= 2

 

(1,4)의 인접한 그룹 : 그룹4

= 1

 

(2,1)의 인접한 그룹 : 그룹2, 그룹3, 그룹5

= 3 + 1 + 1 = 5

 

(2,3)의 인접한 그룹 : 그룹3, 그룹4, 그룹6

= 1 + 1 + 1 = 3

 

(3,0)의 인접한 그룹 : 그룹2, 그룹5

= 3 + 1 = 4

 

(3,2)의 인접한 그룹 : 그룹3, 그룹5, 그룹6

= 1 + 1 + 1 = 3

 

(3,4)의 인접한 그룹 : 그룹4, 그룹6

= 1 + 1 = 2

 

벽인 구역의 값을 10으로 나눈 나머지로 저장한뒤 결과로 출력한다.

4	6	0	0	3
0	0	7	3	2
0	6	0	4	0
5	0	4	0	3

 

 

• BufferedReader를 사용하여 입력 값을 받았습니다.
• StringTokenizer을 이용하여 N,M을 저장하였습니다.
• 0인 지점을 기준으로 BFS탐색으로 그룹을 나누는 bfs함수를 실행하였습니다.
• 각 벽의 지점에서 인접한 그룹의 값을 더하는 wallValue함수를 실행하였습니다.
• 더해진 지도의 값에 10의 나머지 값들을 BufferedWriter에 저장합니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

• bfs함수는 0인 지점을 BFS탐색하여 그룹을 나누었습니다.
• wallValue함수는 벽인 지점의 인접한 그룹의 값을 더해주는 함수입니다.

 

import java.util.*;
import java.io.*;

public class Main {
	//지도에 대한 위치 관련 클래스
    static class position{
        int x, y;
        public position(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
    static int N,M;
    static int[] dx = {0, 0, -1, 1};	//상하좌우 X값 변경값
    static int[] dy = {-1, 1, 0, 0};	//상하좌우 Y값 변경값
    static int[][] map;		//지도 정보 저장 배열
    static int[][] group;	//그룹 정보 저장 배열
    static HashMap<Integer, Integer> groupValue = new HashMap<>();	//그룹 내 0의 개수 저장
    static public void  main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //입력값 처리하는 BufferedReader
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        //결과값 출력하는 BufferedWriter
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        map = new int[N][M];
        group = new int[N][M];
        //지도 관련 정보 저장
        for(int i=0;i<N;i++) {
            String str = br.readLine();
            for (int j = 0; j < M; j++)
                map[i][j] = Character.getNumericValue(str.charAt(j));
        }

        int index = 1;	//첫 그룹 번호
        //각 0인 지점에서 BFS 탐색을 시작으로 그룹 나누기
        for(int i=0;i<N;i++){
            for(int j=0;j<M;j++){
                if(map[i][j] == 0 && group[i][j]==0){
                    groupValue.put(index, bfs(i,j,index));
                    index++;
                }

            }
        }
        //벽에 인접한 그룹의 수 더하기
        for(int i=0;i<N;i++){
            for(int j=0;j<M;j++){
                if(map[i][j]!=0)
                    wallValue(i,j);
                bw.write(map[i][j]%10 + "");	//10으로 나눈 나머지를 BufferedWriter 저장
            }
            bw.write("\n");
        }
        bw.flush();		//결과 출력
        bw.close();
        br.close();
    }
    //0인 지점을 기준으로 BFS탐색으로 그룹을 나누는 함수
    static int bfs(int a, int b, int index){
        Queue<position> queue = new LinkedList<>();
        int result = 1;
        group[a][b] = index;
        queue.add(new position(b,a));
        while(!queue.isEmpty()){
            position cur = queue.poll();
            int x = cur.x;
            int y = cur.y;
            for(int i=0;i<4;i++){
                int tempX = x + dx[i];
                int tempY = y + dy[i];
                if(tempX>=0 && tempY>=0 && tempX<M &&tempY<N){
                    if(map[tempY][tempX]==0 && group[tempY][tempX]==0){
                        group[tempY][tempX] = index;
                        result++;
                        queue.add(new position(tempX,tempY));
                    }
                }
            }
        }
        return result;
    }
    //벽에 인접한 그룹별 값들 더해주는 함수
    static void wallValue(int y, int x){
        HashSet<Integer> check = new HashSet<>();	//인접한 그룹 저장하는 HashSet
        for(int i=0;i<4;i++){
            int tempX = x + dx[i];
            int tempY = y + dy[i];
            if(tempX>=0 && tempY>=0 && tempX<M && tempY<N){
                if(group[tempY][tempX]!=0)
                    check.add(group[tempY][tempX]);
            }

        }
        for(Integer group : check){		//인접한 그룹의 값 더하기
            map[y][x] += groupValue.get(group);
        }
        return;
    }
}