[ 백준 26999 ] Satellite Photographs

1. 문제

26999번: Satellite Photographs

 

2. 풀이

해당 문제는 좌표계에서 BFS를 이용하여 Grouping 하는 기초를 다질 수 있는 문제다. 문제를 요약하자면 아스트리크(*) 로 연결된 가장 넓은 영역을 구하라는 것이다.

 

여기서 조건은 연결되었음을 판단하는 것은 '4 방위로 인접해있는가'다. 이를 풀이하기 위해서는 입력 받은 지도를 순차적으로 순회하면서 아스트리크('*')를 만났을 경우 BFS를 돌려 각 영역의 크기를 구해내면 된다. 당연하게도 방문했던 노드는 다시 방문해서는 안되며, 새로운 아스트리크를 만날 때마다 너비를 증가시키고 최종적으로 여러 구역의 크기 중 가장 큰 영역의 크기를 반환하면 해결!

 

3. 소스코드

 

public class Main {

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

    static int R, C;
    static char[][] map;
    static boolean[][] visit;

    static int solve() {
        int ret = 0;

        for (int i = 0; i < R; i++) {
            for (int j = 0; j < C; j++) {
                if (!visit[i][j] && map[i][j] == '*') {
                    ret = Math.max(ret, search(i, j));
                }
            }
        }

        return ret;
    }

    static int search(int y, int x) {
        Queue<Integer> q = new LinkedList<>();
        q.add(y * C + x);
        visit[y][x] = true;

        int cnt = 1;

        while (!q.isEmpty()) {
            int now = q.poll();
            int nowY = now / C;
            int nowX = now % C;

            for (int dir = 0; dir < 4; dir++) {
                int ny = nowY + dy[dir];
                int nx = nowX + dx[dir];
                if (!canVisit(ny, nx)) continue;
                q.add(ny * C + nx);
                visit[ny][nx] = true;
                cnt++;
            }
        }

        return cnt;
    }

    static boolean canVisit(int y, int x) {
        return 0 <= y && 0 <= x && y < R && x < C && !visit[y][x] && map[y][x] == '*';
    }

    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());
        C = Integer.parseInt(st.nextToken());
        R = Integer.parseInt(st.nextToken());

        map = new char[R][C];
        visit = new boolean[R][C];
        for (int i = 0; i < R; i++) {
            map[i] = br.readLine().toCharArray();
        }

        bw.write(solve() + "");
        bw.flush();
        bw.close();
        br.close();
    }
}

GitHub - kwanik-kor/BOJ: Baekjoon Online Judge - explanation of solved problems and complete code

 

---

BFS 개념은 아래 게시글을 참고♥️

그래프와 BFS(Graph & Breadth First Search)