[백준 11967] 불켜기 - JAVA //le_effort

불켜기

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
2 초	512 MB	3410	933	631	25.650%

문제

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

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

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

입력

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

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

출력

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

예제 입력 1 복사

xxxxxxxxxx
3 6
1 1 1 2
2 1 2 2
1 1 1 3
2 3 3 1
1 3 1 2
1 3 2 1

예제 출력 1 복사

xxxxxxxxxx
5

 

 

 

풀이

bfs를 이용해서 풀었습니다.

 

 

우선 map에 불을 켤 수 있는 정보들을 다 넣어줍니다.

 

문제의 핵심은 갔던 곳을 다시 되돌아가야 된다는 겁니다.

 

아래의 표는 현재 불의상태(이 위치에서 다른 좌표의 불을 킬수 있는 좌표)

예를들어 현재 맵의 상태가 1,1에서 시작하고 불이 켜진 곳에서만 이동 할 수 있으니

 

불 켜짐 (1,2)	불 꺼짐(1,3)	불 꺼짐(2,1)
불 꺼짐(2,2)	불 꺼짐

1,1에서 bfs를 돌리면 범위에서 벗어나지 않는 부분은 총 2곳을 탐색합니다.

1,2와 2,1을 순회 할 수 있습니다.

 

맨 처음 bfs에서는 1,1에서 1,2로 불을 키고 갈 수 있지만 2,1은 갈 수 없습니다.

 

큐에는 1,2가 들어가고 결국 1,3까지는 갈 수 있습니다.

 

여기서 좌표의 (1,3)에서 (2,1)칸의 불을 킬 수 있지만

현재 큐에 있는 좌표는 (1,3)이고 인접한 4방향을 돌려봐야 (2,1)을 도착 할 수 없습니다.

 

그래서 별도의 리스트를 만들어서 불이 꺼져서 못가는 좌표들을 따로 모아두고

불이 켜졌을 때 큐에 다시 넣어주면 됩니다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
​
public class Main {
    static int dx [] = {0,0,1,-1};
    static int dy [] = {1,-1,0,0};
    static boolean visited[][];
    static boolean isPossible[][];
    static ArrayList<Node> map[][];
    static int n,m;
    static int ans =0;
    public static void main(String[] args) throws  IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        
        String [] t = br.readLine().split(" ");
        n = Integer.parseInt(t[0]);
        m = Integer.parseInt(t[1]);
        
        map = new ArrayList[n+1][n+1];
        
        for(int i=1; i<=n; i++) {
            for(int j=1; j<=n; j++) {
                map[i][j] = new ArrayList<>();
            }
        }
        
        
        for(int i=0; i<m; i++) {
            t = br.readLine().split(" ");
            int x = Integer.parseInt(t[0]);
            int y = Integer.parseInt(t[1]);
            int a = Integer.parseInt(t[2]);
            int b = Integer.parseInt(t[3]);
            
            ArrayList<Node>list = map[x][y];
            list.add(new Node(a,b));
        }
    
        bfs();
        System.out.println(ans);
    }
    
    public static void bfs() {
        Queue<Node> q= new LinkedList<>();
        visited = new boolean[n+1][n+1];
        isPossible = new boolean[n+1][n+1];
        ans++;
        ArrayList<Node>waiting = new ArrayList<>();
        visited[1][1]= true;
        isPossible[1][1] =true;
        q.add(new Node(1,1));
        while(!q.isEmpty()) {
            Node a = q.poll();
            
            for(Node light : map[a.x][a.y]) {
                if(!isPossible[light.x][light.y]) {
                    isPossible[light.x][light.y] = true;
                    ans++;
                }
                
            }
            
            
            for(int i=0; i<4; i++) {
                int nx = a.x+dx[i];
                int ny = a.y+dy[i];
                
                if(isRange(nx,ny) && !visited[nx][ny]) {
                    if(isPossible[nx][ny]) {
                        q.add(new Node(nx,ny));
                        visited[nx][ny] = true;
                    }
                    else {
                        waiting.add(new Node(nx,ny));
                    }
                }
            }
            
            
            int size = waiting.size();
            
            for(int i=0; i<size; i++) {
                Node poll = waiting.get(i);
                if(isPossible[poll.x][poll.y] && !visited[poll.x][poll.y]) {
                    q.add(new Node(poll.x,poll.y));
                    visited[poll.x][poll.y] = true;
                }
            }
        }
        
    }
    public static boolean isRange(int x, int y) {
        if(x>=1 && y>=1 && x<=n && y<=n) {
            return true;
        }
        return false;
    }
}
class Node{
    int x,y;
    Node(int x, int y){
        this.x=x;
        this.y=y;
    }
}