백준 : 16946

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

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

하나의 정점에서 BFS를 탐색을 한다면 시간초과걸린다 일단 모든 정점을 0으로 이어저있는칸의 구간별로 개수를 센다. 이렇게 모든 값을 매긴다음 1을 기준으로 구역이 인접해있는지센다. 잇때 set을 쓰는데 같은 구역에서는 중복해서 더하면  안되기 때문이다. 이런 최적화 문제도 자주 푸는것이 좋을거 같다.

package day0311;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
import java.util.TreeSet;
 
public class B16946 {
    static int N, M;
    static char[][] map;
    static int[][] Answer;
    static int[][] cntMap;
    static int dy[] = { 1, -1, 0, 0 };
    static int dx[] = { 0, 0, 1, -1 };
    static ArrayList<Integer> cnt = new ArrayList<Integer>();
    static int num;
 
    static class Pair {
        int y;
        int x;
 
        public Pair(int y, int x) {
            super();
            this.y = y;
            this.x = x;
        }
    }
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        cnt.add(0);
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
 
        map = new char[N][M];
        Answer = new int[N][M];
        cntMap = new int[N][M];
        num = 1;
 
        for (int i = 0; i < N; i++) {
            map[i] = br.readLine().toCharArray();
        }
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
 
                if (map[i][j] == '0' && cntMap[i][j]==0) {
                    cntMap[i][j] = num;
 
                    Queue<Pair> q = new LinkedList<>();
                    q.add(new Pair(i, j));
                    int thisCnt =0;
                    while (!q.isEmpty()) {
                        Pair cur = q.poll();
                        thisCnt++;
 
                        for (int d = 0; d < 4; d++) {
                            int ny = cur.y + dy[d];
                            int nx = cur.x + dx[d];
                            if (ny < 0 || nx < 0 || ny >= N || nx >= M)
                                continue;
                            if (map[ny][nx] == '1')
                                continue;
                            if (cntMap[ny][nx] != 0)
                                continue;
                            cntMap[ny][nx] = num;
                            q.add(new Pair(ny, nx));
                        }
                    }
                    cnt.add(thisCnt);
                    num++;
                }
            }
        }
        
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if(map[i][j]=='1') {
                    TreeSet<Integer> set = new TreeSet<Integer>();
                    for(int d=0;d<4;d++) {
                        int ny = i+dy[d];
                        int nx = j+dx[d];
                        if(ny<0||nx<0||ny>=N||nx>=M)continue;
                        if(cntMap[ny][nx]==0)continue;
                        set.add(cntMap[ny][nx]);
                    }
                    Iterator<Integer> it = set.iterator();
                    while(it.hasNext()) {
                        Answer[i][j]+=cnt.get(it.next());
                    }
                    sb.append((Answer[i][j]+1)%10);
                }else {
                    sb.append(0);
                }
            }
            sb.append("\n");
        }
 
        System.out.print(sb.toString());
 
    }
}