백준 2234 (성곽) - java

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

2234번: 성곽

(1 , 2 , 4 , 8 -> 서 북 동 남)에 성곽이 있는 경우이다.

15에서 주어진 값을 빼고 '남'쪽부터 성곽이 없는 곳을 찾는 방식으로 이동의 경우를 구할 수 있다.

 

1. 성의 개수

• 2차원 좌표계를 기준으로 BFS 함수를 방문하지 않은 기점을 중심으로 수행하여 함수가 실행된 횟수를 구한다면 성의 개수를 구할 수 있다.

2. 가장 큰 성의 크기

• 위의 1을 구하기 위한 함수내에서 한번 함수가 실행 될 때 탐색된 좌표의 크기의 최댓값을 구하면 된다.

3. 벽을 통과

• 쉽게 생각한다면 각 성을 연결하기 위해서는 무조건 1개의 벽을 부시면 된다. 
• 각 성의 크기를 2번에서 구해놨기 때문에 서로 다른 성이 붙어 있는 경우 그 크기의 합의 최댓값을 구하면 된다.

 

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

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

    // 서 북 동 남
    static int[] dx = {0,-1,0,1};
    static int[] dy = {-1,0,1,0};
    static int[] w = {1,2,4,8};

    static int first = 1;
    static int second = 0;
    static int three = 0;
    static HashMap<Integer,Integer> map = new HashMap<>();
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        m = Integer.parseInt(st.nextToken());
        n = Integer.parseInt(st.nextToken());

        for(int i=1;i<=n;i++)
        {
            st = new StringTokenizer(br.readLine()," ");
            for(int j=1;j<=m;j++)
            {
                board[i][j] = 15 - Integer.parseInt(st.nextToken()); // 열려있는 성문을 확인
            }
        }
        int start = 1;
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=m;j++)
            {
                if(visit[i][j]==0)
                {
                    int tmp = bfs(i,j,start);
                    map.put(start,tmp);
                    first = start; // 1번 답을 위해 갱신
                    second = Math.max(second , tmp); // 2번 답 갱신
                    start = start + 1;
                }
            }
        }

        third(); // 3번 구하는 함수

        System.out.println(first);
        System.out.println(second);
        System.out.println(three);
        br.close();
    }

    static int bfs(int x,int y,int num) // num = 성의 번호
    {
        int count = 1;
        Queue<point> q = new LinkedList<>();
        visit[x][y] = num;
        q.add(new point(x,y));

        while(!q.isEmpty())
        {
            point cur = q.poll();
            int tmp = board[cur.x][cur.y];

            for(int i=3;i>=0;i--)
            {
                if(tmp-w[i] < 0) // 해당 성문이 막혀있는 경우
                    continue;

                int nx = cur.x + dx[i];
                int ny = cur.y + dy[i];

                if(nx>=1&&nx<=n&&ny>=1&&ny<=m)
                {
                    if(visit[nx][ny]==0)
                    {
                        visit[nx][ny] = num; // num번 째 성이라고 표시
                        q.add(new point(nx,ny));
                        count = count + 1;
                    }
                }

                tmp = tmp - w[i]; // 다음 성문 확인
            }
        }

        return count;
    }

    static void third()
    {
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=m;j++)
            {
                for(int k=0;k<4;k++)
                {
                    int nx = i + dx[k];
                    int ny = j + dy[k];

                    if(nx>=1&&ny>=1&&nx<=n&&ny<=m)
                    {
                        if(visit[i][j]!=visit[nx][ny]) // 다른 번호의 성인 경우
                        {
                            // 벽을 부셔 연결했을 때 크기
                            int tmp = map.get(visit[i][j]) + map.get(visit[nx][ny]);

                            three = Math.max(three, tmp);
                        }
                    }
                }
            }
        }
    }

    static void print()
    {
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=m;j++)
            {
                System.out.print(visit[i][j]+" ");
            }
            System.out.println();
        }
    }
}
class point
{
    int x;
    int y;
    point(int x,int y)
    {
        this.x = x;
        this.y = y;
    }
}