백준 16946 (벽 부수고 이동하기 4) - java

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

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

문제

우선 고려해야 할점은 시간이다. 모든 좌표에서 BFS를 반복적으로 실행한다면 시간 초과가 뜰 것이다.

사실 내 결과도 만족스러운 시간은 아니지만 지금 당장 저것보다 줄이는 걸 생각하기엔 어렵다.....

 

방법

• 우선 0(이동 가능한 지점) 에 대하여 BFS를 진행한다. 그리고 여러 영역이 존재할 것이기 때문에 각 영역에 대하여 구분할 수 있는 번호를 지정하고 방문 배열을 해당 영역 번호로 채운다. 아래 사진에서 idx라는 변수를 사용하여 영역을 지정하였다 !

• 그리고 BFS 함수의 결과값으로 방문한 좌표의 개수를 반환 받고 HashMap에 키 - 영역 번호 , 값 - 좌표 개수 형태로 저장한다.

결과 좌표 만드는 코드

for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=m;j++)
            {
                if(board[i][j]==0)
                    result[i][j] = 0;

                else{
                    HashSet<Integer> numbers = new HashSet<>(); // 영역 번호 중복 방지
                    for(int k=0;k<4;k++)
                    {
                        int nx = i + dx[k];
                        int ny = j + dy[k]; // 4방위만 검사

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

                        if(visit[nx][ny]==0)
                            continue;

                        numbers.add(visit[nx][ny]); // set에 추가
                    }

                    result[i][j] = 1;
                    for(int cur : numbers)
                    {
                        result[i][j] += map.get(cur); // 갱신
                    }

                    result[i][j] = result[i][j] % 10; 
                }
            }
        }

전체 코드

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

public class Main {
    static int n = 0;
    static int m = 0;
    static int[][] board;

    static int[] dx = {0,0,-1,1};
    static int[] dy = {1,-1,0,0};

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        board = new int[n+1][m+1];

        ArrayList<point> zero = new ArrayList<>();
        for(int i=1;i<=n;i++)
        {
            String line = br.readLine();
            for(int j=1;j<=m;j++)
            {
                board[i][j] = Integer.parseInt(line.charAt(j-1)+"");

                if(board[i][j]==0)
                    zero.add(new point(i,j));
            }
        }

        int[][] visit = new int[n+1][m+1];

        int idx = 1;
        HashMap<Integer,Integer> map = new HashMap<>();

        for(point cur : zero)
        {
            if(visit[cur.x][cur.y]==0)
            {
                int count = bfs(cur.x,cur.y,board,visit,idx);
                map.put(idx,count);
                idx = idx + 1;
            }
        }

        int[][] result = new int[n+1][m+1];

        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=m;j++)
            {
                if(board[i][j]==0)
                    result[i][j] = 0;

                else{
                    HashSet<Integer> numbers = new HashSet<>();
                    for(int k=0;k<4;k++)
                    {
                        int nx = i + dx[k];
                        int ny = j + dy[k];

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

                        if(visit[nx][ny]==0)
                            continue;

                        numbers.add(visit[nx][ny]);
                    }

                    result[i][j] = 1;
                    for(int cur : numbers)
                    {
                        result[i][j] += map.get(cur);
                    }
                    
                    result[i][j] = result[i][j] % 10;
                }
            }
        }

        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=m;j++)
            {
                bw.write(result[i][j]+"");
            }bw.write("\n");
        }

        bw.flush();
        bw.close();
        br.close();
    }


    static int bfs(int x,int y,int[][] board,int[][] visit,int num)
    {
        visit[x][y] = num;
        int count = 1;
        Queue<point> q = new ArrayDeque<>();
        q.add(new point(x,y));

        while(!q.isEmpty())
        {
            point cur = q.poll();

            for(int i=0;i<4;i++)
            {
                int nx = cur.x + dx[i];
                int ny = cur.y + dy[i];

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

                if(visit[nx][ny]!=0)
                    continue;

                if(board[nx][ny]==0)
                {
                    visit[nx][ny] = num;
                    q.add(new point(nx,ny));
                    count = count + 1;
                }
            }
        }

        return count;
    }
}
class point
{
    int x;
    int y;

    point(int x,int y)
    {
        this.x = x;
        this.y = y;
    }
}