[자바] 백준 11967 - 불켜기 (java)

 문제 : boj11967

---

 

필요 알고리즘 개념

• BFS, DFS 등의 그래프 탐색 알고리즘
  
  • 그래프 탐색을 통해 풀 수 있다.

※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다.

 

---

 

풀이

  우선 BFS를 모른다면 'BFS 알고리즘 (너비 우선 탐색)' 글을 참고하자.

로직을 정확히 세워서 그래프 탐색을 진행하면 풀 수 있다. 글로 설명하면 아래와 같다.

 

  우선 각 방의 상태를 다음과 같이 설정하였다.

- 미방문 : 0

- 불 켜져있음 : 1

- 이미 방문함 : 2

- 불켜져있는 방과 상하좌우로 인접해있음 : 3

 

  로직은 다음과 같다. 최종적으로 출력할 값은 cnt이다. cnt는 처음에 (1,1) 지점은 켜져있으므로 1이다. q는 큐로, 다음 방문할 불이 켜져있는 방들에 해당한다.

  더이상 방문할 곳이 없을때까지 이하를 진행한다.

 

방문 가능한 특정 위치를 방문한다. (코드에서 cur)

해당 위치에서 불을 켤 수 있는 방 목록을 각각 살펴본다.

___ 이미 방문했거나, 이미 불이 켜져있다면 무시한다. (방 목록의 다음 방으로)

___ 그렇지 않다면 cnt를 1 증가시킨다.

___ 불켜져있는 방과 상하좌우로 인접해있는 방이라면 q에 추가해주고, 이미 방문했다고 체크한다.

___ 그렇지 않다면 '불 켜져있음'으로 체크해둔다.

이제 상하좌우로 인접한 방들을 살펴본다.

___ 이미 방문했거나, 이미 불켜져있는 방과 상하좌우로 인접했다고 체크했다면 무시한다. (다음 인접한 방으로)

___ 불이 켜져있다면 q에 추가해주고, 다음 인접한 방을 보러 간다.

___ 그렇지 않다면 '불켜져있는 방과 상하좌우로 인접해있음'으로만 체크해둔다.

cnt를 출력한다.

 

---

 

코드 : github

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

public class Main {
    private static final BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    private static final int[] DR = {0, 0, 1, -1};
    private static final int[] DC = {1, -1, 0, 0};
    private static final int ON = 1;
    private static final int CANDIDATE = 3;
    private static final int VISITED = 2;


    public static void main(String[] args) throws Exception {
        new Main().solution();
    }

    public void solution() throws Exception {
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        Map<Pos, List<Pos>> map = new HashMap<>();
        while (m-->0) {
            st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            Pos cur = new Pos(x, y);
            if (map.containsKey(cur)) {
                map.get(cur).add(new Pos(a, b));
            } else {
                List<Pos> list = new ArrayList<>();
                list.add(new Pos(a, b));
                map.put(cur, list);
            }
        }

        Queue<Pos> q = new ArrayDeque<>();
        int[][] v = new int[n+1][n+1];
        v[1][1] = VISITED;
        q.add(new Pos(1, 1));
        int cnt = 1;
        while (!q.isEmpty()) {
            Pos cur = q.poll();
            if (map.containsKey(cur)) {
                for (Pos light : map.get(cur)) {
                    if (v[light.r][light.c] == VISITED || v[light.r][light.c] == ON) continue;
                    cnt++;
                    if (v[light.r][light.c] == CANDIDATE) {
                        q.add(light);
                        v[light.r][light.c] = VISITED;
                    } else {
                        v[light.r][light.c] = ON;
                    }
                }
            }

            for (int d = 0; d < 4; d++) {
                int nr = cur.r + DR[d];
                int nc = cur.c + DC[d];
                if (nr < 1 || nr > n || nc < 1 || nc > n || v[nr][nc] == VISITED || v[nr][nc] == CANDIDATE) continue;

                if (v[nr][nc] == ON) {
                    v[nr][nc] = VISITED;
                    q.add(new Pos(nr, nc));
                    continue;
                }

                v[nr][nc] = CANDIDATE;
            }
        }
        System.out.println(cnt);
    }
}

class Pos {
    int r, c;
    public Pos(int r, int c) {
        this.r = r;
        this.c = c;
    }

    @Override
    public int hashCode() {
        return c*20000+r;
    }

    @Override
    public boolean equals(Object obj) {
        Pos other = (Pos) obj;
        return this.r == other.r && this.c == other.c;
    }
}