Baekjoon 11967 불켜기 JAVA

11967번: 불켜기

문제

농부 존은 최근에 N × N개의 방이 있는 거대한 헛간을 새로 지었다. 각 방은 (1, 1)부터 (N,N)까지 번호가 매겨져있다(2 ≤ N ≤ 100). 어둠을 무서워하는 암소 베시는 최대한 많은 방에 불을 밝히고 싶어한다.

베시는 유일하게 불이 켜져있는 방인 (1, 1)방에서 출발한다. 어떤 방에는 다른 방의 불을 끄고 켤 수 있는 스위치가 달려있다. 예를 들어, (1, 1)방에 있는 스위치로 (1, 2)방의 불을 끄고 켤 수 있다. 베시는 불이 켜져있는 방으로만 들어갈 수 있고, 각 방에서는 상하좌우에 인접한 방으로 움직일 수 있다. 

베시가 불을 켤 수 있는 방의 최대 개수를 구하시오.

 

map별 스위치 정보가 주어졌을때 킬수있는 방의 개수를 구하는 문제.

조건

[입력]

첫 번째 줄에는 N(2 ≤ N ≤ 1 00)과, M(1 ≤ M ≤ 20,000)이 정수로 주어진다.

다음 M줄에는 네 개의 정수 x, y, a, b가 주어진다. (x, y)방에서 (a, b)방의 불을 켜고 끌 수 있다는 의미이다. 한 방에 여러개의 스위치가 있을 수 있고, 하나의 불을 조절하는 스위치 역시 여러개 있을 수 있다. 

[출력]

베시가 불을 켤 수 있는 방의 최대 개수를 출력하시오.

풀이

해당 문제는 구현 문제로 시키는 대로 잘 구현하면 된다. 다만 값을 저장하는 부분을 어떤 식으로 해야 할지 의문이 들었고 2차원 배열 리스트를 이용해서 저장하고 사용할 수 있었다.

로직은 아래와 같은 순서로 구현하였다.

1. list에 값을 넣을 때 1,1에서 가는 애들은 값을 넣지 않고 바로 all_q(불 켜야 하는 큐)에 넣어준다.

2. 반복문을 돌린다.

3. all_q가 비었는지 체크하고 비면 반복문을 빠져나온다.

4. all_q에 들어있는 걸 빼내면서 이미 불을 켰는지 체크하고 안 켰으면 불키고 카운트 증가시킨다.

5. 이제 1,1부터 map를 탐색하면서 이동하고 여기서 최초 방문하는 애들만 다시 all_q에 담아준다.

2~5번 로직을 계속 방문하여 준다.

방문 체크를 큐에서 방문 체크하는 용 하나와 전체적으로 최초 방문을 체크하는 거 하나를 사용하다 보니 구현하면서 많이 헷갈려서 계속 정리하면서 문제를 해결했다. 

정리했던 내용

이거 음 저거 좌표를 우선순위 큐에 넣는다? 
이걸 데이터를 어디에 넣어야 하는데
어디다 넣지 음...
일단 정렬해

1112
1113
1312
1321
2122
2331

1. 첨에 데이터 입력하면서 1,1 해당하는 거 모두 이동 가능으로 바꿈
2. 이제 1,1에서 이동해봄 이때 간 곳들 모두 어디에 담음
3. 어디에 담은 거 가지고 해당하는 애들 다시 불킴
4. 또 이동하면서 담음 만약 담는 게 널이면 종료

데이터는 리스트를 2차원 배열로 만들고 add 하는 방식으로 진행

1. 입력 데이터를 입력하면서 1,1,에 대해서 큐에 담음
 1-1 큐 비면 종료
2. 큐에 담은 거 빼내서 map 1 -> 0으로 

2. 1,1에서 bfs를 돌린다. 방문 배열 visit를 체크함 + on 배열 갱신 카운트 증가.
3. 방문하면 on 배열 true로 갱신 만약 이미 true면 cnt 증가 안 시킴 큐에 담음
 

입력 처음에 1,1에서 갈 수 있는 거를 all큐에 담아
1. all큐가 비었는지 체크 비었으면 멈춤
2. all큐에 담길걸 빼내고 불 켜졌는지 체크 불키고 카운트 1 증가 
3. 1,1에서 방문해 visit로 방문 체크하면서 근데 만약 allvisit 이 false인데 방문했으면 all에 담아줘 방문 체크도

디버깅 필수!

코드

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

public class Main {

	static int N, M, cnt = 1, dy[]= {-1,1,0,0} , dx[]= {0,0,-1,1};
	static boolean[][] map, visit, all_visit; //불이 켜진 맵, bfs용 방문체크, 최종 방문체크
	static ArrayList<Node>[][] list; //리스트를 2차원 배열로 만들고 안에 값을 넣는다.
	static Queue<Node> all_q = new LinkedList<>(); // 불 켜야하는 애들
	static Queue<Node> q = new LinkedList<>(); // bfs용
	public static void main(String[] args) throws Exception{
		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 boolean[N][N];
		all_visit = new boolean[N][N];
		list = new ArrayList[N][N];
		for (int i = 0; i < N; i++) { // 리스트 배열 초기화
			for (int j = 0; j < N; j++) {
				list[i][j] = new ArrayList<>();
			}
		}
		for (int i = 0; i < M; i++) {
			st = new StringTokenizer(br.readLine());
			int sY = Integer.parseInt(st.nextToken()) -1; // 문제는 1,1부터지만 0,0을 시작으로 하기위해
			int sX = Integer.parseInt(st.nextToken()) -1;
			int eY = Integer.parseInt(st.nextToken()) -1;
			int eX = Integer.parseInt(st.nextToken()) -1;
			if(sY + sX == 0) { // 더한값이 0이면 0,0인 상태 갈수있는곳 먼저 큐에 담음
				all_q.offer(new Node(eY,eX));
				continue;
			}
			list[sY][sX].add(new Node(eY,eX)); // 리스트에 값 추가해주기
		}

		map[0][0] = true; //map과 최종 방문체크를 true해줌
		all_visit[0][0] = true;
		while(true) {
			if(all_q.isEmpty()) // 큐가 비었으면 종료
				break;
			switch_on(); // 불을 켜준다
			bfs(); // bfs 돌림
		}
		System.out.println(cnt);
	}
	
	private static void bfs() {
		q.add(new Node(1,1)); // 시작점 갱신
		visit = new boolean[N][N]; // bfs용 방문체크 갱신
		while(!q.isEmpty()) {
			Node n = q.poll();
			for (int i = 0; i < 4; i++) {
				int ny = n.y + dy[i];
				int nx = n.x + dx[i];
				if(ny < 0 || nx < 0 || ny >= N || nx >= N || !map[ny][nx] || visit[ny][nx])
					continue;
				if(!all_visit[ny][nx]) { // 처음 방문인 경우
					all_visit[ny][nx] = true; // 방문 체크
					all_q.addAll(list[ny][nx]); // 리스트에서 해당 좌표에서 갈수있는애들 모두 불켜라고 등록
				}
				visit[ny][nx] = true;	
				q.add(new Node(ny,nx));
			}
		}
	}

	private static void switch_on() {
		while(!all_q.isEmpty()) { // 불켜야할거 있는지 체크
			Node n = all_q.poll();
			if(!map[n.y][n.x]) { // 이미 불 켜져있는지 체크
				map[n.y][n.x] = true; // 불 키고 카운트 증가
				cnt++;
			}
		}
	}

	static class Node{
		int y, x;
		Node(int y, int x){
			this.y = y;
			this.x = x;
		}
	}
}

 

GitHub - JUNGSOONIL/Algorithm-JAVA: 알고리즘 문제 해결 자바 소스 코드