윤주

윤주

꾸준히 기록하자

BOJ 11967 불켜기

메모리 : 195384 KB

시간 : 704 ms


풀이

문제에서 인접한 상하좌우로만 이동이 가능하에서 BFS나 DFS 탐색이라고 생각했다.

힌트를 보니 방문했던 곳을 다시 방문할 수 있기에, 어떻게 그걸 가능하게 할까 고민했다.

불이 켜진 개수에 따라 다시 이동할 수 있게 해야겠다고 생각해서 방문 배열을 3차원 배열로 만들었다.

한 방에서 여러 개의 스위치가 있을 수 있기 때문에 ArrayList 배열을 이용하여 map을 만들었다.

그 후 각 위치에서 불을 킬 수 있는 방들의 위치가 있을때마다 추가해주었다.

또한 각 방의 불이 켜져있는지 아닌지 boolean 타입 배열을 선언해주었다.

이렇게 해서 방문 점검 배열, 스위치를 저장하고 있는 배열, 불이 켜졌는지 확인하는 배열, 총 3개의 배열을 사용했는데 이게 메모리에 엄청난 영향을 준 것 같다.

BFS를 돌며 큐에서 하나 빼낼때마다, 그 방에서 켤 수 있는 모든 방들의 불을 켜준뒤 light 변수를 1씩 증가시켜주었다.


느낀점

메모리와 시간이 어마어마하다.

다른 사람들은 DFS로 풀고 3차원 배열도 안 썼던데 한 번 고민해보면 좋을 것 같다.


코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class BOJ11967 {
  static int N, M;
  static ArrayList<Pos>[][] map; // 어느 방의 불을 켤 수 있는지 저장
  static boolean[][] room; // 불이 켜져있는지
  static boolean[][][] visited; // 방문확인
  static int light; // 불 켜진 방의 개수
  static int[][] dir = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st = new StringTokenizer(br.readLine(), " ");
    N = Integer.parseInt(st.nextToken());
    M = Integer.parseInt(st.nextToken());
	
    map = new ArrayList[N+1][N+1];
    room = new boolean[N+1][N+1];
    visited = new boolean[N+1][N+1][10000];
	
    for (int i = 0; i < M; i++) {
      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());
		
      if(map[x][y] == null) {
    	map[x][y] = new ArrayList<Pos>();
      }
      map[x][y].add(new Pos(a, b));
    } // end for
		
    light = 1;
    visited[1][1][light] = true;
    room[1][1] = true;
    Queue<Pos> q = new LinkedList<Pos>();
    q.offer(new Pos(1, 1));
      while(!q.isEmpty()) {
    	// 현재 위치에서 불을 킬 수 있는 장소들 불을 킨다
    	Pos cur = q.poll();
    	if(map[cur.x][cur.y] != null) { // 불 켤 수 있는 스위치가 존재한다면
    	  for (int i = 0; i < map[cur.x][cur.y].size(); i++) {
            Pos next = map[cur.x][cur.y].get(i);
            if(room[next.x][next.y] == false) {
              room[next.x][next.y] = true; // 불을 켜주고
              light++; // 불켜진 방의 개수를 증가시킨다
            }
          }
        } // end if
			
        // 불이 켜져있는 곳으로 상하좌우 이동한다
        for (int i = 0; i < 4; i++) {
          int nx = cur.x + dir[i][0];
          int ny = cur.y + dir[i][1];
          if(isIn(nx, ny) && !visited[nx][ny][light] && room[nx][ny]) { // 범위 내에 있고, 방문한 적 없고, 불이 켜져있다면 이동
            visited[nx][ny][light] = true;
            q.offer(new Pos(nx, ny));
          }
        } // end for
      } // end while 
		
      System.out.println(light);
  }
	
  public static boolean isIn(int x, int y) {
    return x>=1 && x<=N && y>=1 && y<=N;
  }
	
  static class Pos {
    int x, y;

    public Pos(int x, int y) {
      super();
      this.x = x;
      this.y = y;
    }

    @Override
    public String toString() {
      return "Pos [x=" + x + ", y=" + y + "]";
    }
  }
}

참고