백준 11967번: 불켜기 (Java)

접근

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

11967번: 불켜기

간단한 bfs 알고리즘 문제였습니다.

LinkedList[N][N] 배열을 만들어 해당 위치에서 켤 수 있는 위치를 저장해주고, visited 배열에는 0, 1, 2로 구분하여 0일 경우 어두운 상태, 1일 경우 스위치로 불이 밝혀진 상태, 2일 경우 이미 베시가 방문한 상태를 뜻하도록 상태를 저장해줍니다.

한가지 주의할 점은 베시가 새로운 곳으로 이동하여 불을 켰을 때, 불이 켜진 해당 지점의 4방향을 탐색하여 visited 값이 2일 경우, 즉 베시가 이미 방문했던 위치가 있을 경우 queue에 다시 한번 추가해줍니다. 그렇지 않으면 베시가 이미 지나간 위치에서 새로운 불이 들어온 경우를 bfs 탐색이 불가능하기 때문입니다.

코드

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

public class Main {

  static class Node {

    private int r, c;

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

  static int N, M, ans;
  static int[] dr = { 0, 1, 0, -1 };
  static int[] dc = { 1, 0, -1, 0 };
  static int[][] visited;
  static LinkedList<Node>[][] lightSwitch;

  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    String[] input = br.readLine().split(" ");
    N = Integer.parseInt(input[0]);
    M = Integer.parseInt(input[1]);
    visited = new int[N + 1][N + 1];
    lightSwitch = new LinkedList[N + 1][N + 1];
    for (int i = 0; i <= N; i++) {
      for (int j = 0; j <= N; j++) {
        lightSwitch[i][j] = new LinkedList<>();
      }
    }
    for (int i = 0; i < M; i++) {
      input = br.readLine().split(" ");
      lightSwitch[Integer.parseInt(input[0])][Integer.parseInt(input[1])].add(new Node(Integer.parseInt(input[2]), Integer.parseInt(input[3])));
    }
    br.close();
    bfs();
    System.out.println(ans);
  }

  static void bfs() {
    LinkedList<Node> queue = new LinkedList<>();
    visited[1][1] = 2;
    queue.add(new Node(1, 1));
    ans = 1;
    while (!queue.isEmpty()) {
      Node now = queue.poll();
      while (!lightSwitch[now.r][now.c].isEmpty()) {
        Node target = lightSwitch[now.r][now.c].poll();
        if (visited[target.r][target.c] == 0) {
          ans++;
          visited[target.r][target.c] = 1;
          for (int i = 0; i < 4; i++) {
            int nr = target.r + dr[i];
            int nc = target.c + dc[i];
            if (mapOut(nr, nc)) continue;
            if (visited[nr][nc] == 2) queue.add(new Node(nr, nc));
          }
        }
      }
      for (int i = 0; i < 4; i++) {
        int nr = now.r + dr[i];
        int nc = now.c + dc[i];
        if (mapOut(nr, nc)) continue;
        if (visited[nr][nc] == 1) {
          queue.add(new Node(nr, nc));
          visited[nr][nc] = 2;
        }
      }
    }
  }

  static boolean mapOut(int r, int c) {
    return (r < 1 || N < r || c < 1 || N < c);
  }
}

더 생각해 볼 것?

...

코드나 내용 관련 조언, 부족한 점 및 질문 언제든 환영합니다!