백준 11967 <불켜기>

그래프 문제이긴 하지만 일반적인 BFS와 DFS랑은 다르게 생각이 필요한 문제였다.

 

이동을 할 때 불이 켜져 있으면 이동이 가능하기 때문에 이동을 할 수 있는 위치가 불이 켜져 있으면 계속 진행해주도록 생각해줘야 하는 문제이다.

 

문제 풀이

1. 큐에서 꺼내 그 지점에서 불을 켜준다.
2. 그리고 이동한 장소에서 4방향을 갈수 있다고 표시해준다.
3. 이동할 장소를 표시한 이차원배열에서 불이 켜져 있고 방문을 안 했고 이동할 수 있다면 큐에 넣어준다.

즉 불을 키고 이동할 장소인지 계속 찾아주는 전체 탐색인 것이다.

 

생각해보니 총 맵의 크기가 100*100 이므로 제곱을 돌아도 1억이므로 시간이 넘치지 않는다.

 

이러한 예제가 주어진다면 처음 시작은 이러할 것이다.

이런 흐름으로 진행 될것이고 2,2는 킬 수 있는 것이 없으니 총 5개다.

 

이렇게 흐름이 진행되고 마지막에 count가 true인 개수를 세어주면 불 켜진 최대수이다.

 

전체 코드

import java.awt.Point;
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 Main {

	static ArrayList<Point> have[][];
	static boolean visit[][],check[][],count[][];
	static int n, m, dir[][] = { { -1, 0 }, { 0, 1 }, { 1, 0 }, { 0, -1 } }, result;
	static Queue<Point> q;

	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());
		have = new ArrayList[n][n];
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				have[i][j] = new ArrayList<Point>();
			}
		}
		visit = new boolean[n][n];//방문여부
		check=new boolean[n][n];//불켜지고 이동이 가능한지
		count=new boolean[n][n];//불킨것
		for (int i = 0; i < m; i++) {
			st = new StringTokenizer(br.readLine());
			int x = Integer.parseInt(st.nextToken()) - 1;
			int y = Integer.parseInt(st.nextToken()) - 1;
			have[x][y].add(new Point(Integer.parseInt(st.nextToken()) - 1, Integer.parseInt(st.nextToken()) - 1));
		}
		result = 0;
		q= new LinkedList<Point>();
		visit[0][0] = true;
		count[0][0]=true;
		q.add(new Point(0, 0));
		bfs();
		for(int i=0;i<n;i++) {
			for(int j=0;j<n;j++) {
				if(count[i][j]) {
					result++;
				}
			}
		}
		System.out.println(result);
	}

	private static void bfs() {
		// TODO Auto-generated method stub
		while (!q.isEmpty()) {//가질 수 있는 키 다 담아서 체크하기
			Point next=q.remove();
			for(int i=0;i<have[next.x][next.y].size();i++) {
				Point nextp=have[next.x][next.y].get(i);
				if(count[nextp.x][nextp.y]) {
					continue;
				}
				count[nextp.x][nextp.y]=true;
			}//불 키는것
			for(int i=0;i<4;i++) {
				int x1=next.x+dir[i][0];
				int y1=next.y+dir[i][1];
				if(x1<0||x1>=n||y1<0||y1>=n) {
					continue;
				}
				check[x1][y1]=true;
			}
			for(int i=0;i<n;i++) {
				for(int j=0;j<n;j++) {
					if(check[i][j]&&count[i][j]&&!visit[i][j]) {
						visit[i][j]=true;
						q.add(new Point(i,j));
					}
				}
			}
		}
	}
}