[백준] 16946번 : 벽 부수고 이동하기 4

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

---

[BFS]

Time Limit Exceeded(TLE)를 높은 확률로 만날 수 있는 문제이다. 여러 가지 방식으로 문제를 풀어봤으나 매번 시간 초과... 결국 AC를 받은 것은 다음과 같은 방법이다.

 

* 갈 수 있는 칸을 저장하는 int[][] move

* 빈 공간에 대해 방문 체크 boolean[][] visit

* 벽에 대해 방문 체크 boolean[][] wall

* 지도 저장 int[][] map

 

1. 입력을 받으며 벽인 곳의 move는 1로 세팅

2. 2중 루프를 돌며 빈 공간인 곳에 대해 BFS를 실시.

2-1. 갈 수 있는 빈 공간의 개수를 세고, 마주치는 벽의 정보를 List에 저장

3. BFS 종료 후 마주친 벽에 저장해둔 빈 공간의 개수를 더함

 

2 ~ 3 반복

 

처음에는 빈 공간의 개수를 만난 벽들에 더해주는 것이 아닌, 각각의 빈 공간이 그 주변의 빈 공간 개수를 저장하는 식으로 했다. 결과적으로 불필요한 반복을 더 하게 되어 시간초과를 만났다.

 

(+추가)

출력하는 부분에 있어서 System.out을 이용한 출력을 사용해왔는데, 이 문제처럼 출력할 수가 많아지면 StringBuilder를 이용하는 것이 시간단축에 있어 더 좋다는 글을 보고 추가로 작성한다. 실제로 System.out 을 사용해서 출력을 했을 떄와 확연하게 차이가 난다.

        for(int i=1; i<=n; i++){
            StringBuilder builder = new StringBuilder();
            
            for(int j=1; j<=m; j++)
                builder.append(move[i][j] % 10);
                
            System.out.println(builder.toString());
        }

# Code </>

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

public class Main {

    static class Point {
        int y, x;
        public Point(int yy, int xx) {
            y = yy;
            x = xx;
        }
    }

    static int[][] map = new int[1001][1001], move = new int[1001][1001];
    static boolean[][] visit = new boolean[1001][1001], wall = new boolean[1001][1001];
    static int[] Y = {-1, 1, 0, 0}, X = {0, 0, -1, 1};
    static int n, m;

    static void BFS() {

        Queue<Point> Q = new LinkedList<>();
        List<Point> list = new ArrayList<>();

        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= m; j++) {

                int cnt = 1;
                if (!visit[i][j] && map[i][j] == 0) {
                    list.clear();
                    visit[i][j] = true;
                    Q.add(new Point(i, j));

                    while (!Q.isEmpty()) { //빈 공간의 개수 구하기
                        Point p = Q.poll();
                        int y = p.y;
                        int x = p.x;

                        for (int a = 0; a < 4; a++) {
                            int ny = y + Y[a];
                            int nx = x + X[a];

                            if (ny < 1 || nx < 1 || ny > n || nx > m || visit[ny][nx]) continue;

                            if(map[ny][nx] == 1){
                                if(!wall[ny][nx]) {
                                    list.add(new Point(ny, nx)); //주변 벽의 좌표 저장
                                    wall[ny][nx] = true;
                                }
                                continue;
                            }

                            cnt++;
                            visit[ny][nx] = true;
                            Q.add(new Point(ny, nx));
                        }
                    }
                    for(Point p:list) { //저장한 벽에 빈 공간 개수 더해줌
                        move[p.y][p.x] += cnt;
                        wall[p.y][p.x] = false;
                    }
                }
            }
    }

    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());

        for(int i=1; i<=n; i++){
            char[] str = br.readLine().toCharArray();
            for(int j=1; j<=m ;j++) {
                map[i][j] = str[j - 1] - '0';

                if(map[i][j] > 0)
                    move[i][j] = 1;
            }
        }

        BFS();

        for(int i=1; i<=n; i++){
            for(int j=1; j<=m; j++)
                System.out.print(move[i][j] % 10);
            System.out.println();
        }
    }
}