티스토리 뷰

PS/Problem_Solving

[BOJ] 11967.불켜기(완탐).java

Aaron 2020. 11. 12. 00:33
반응형


#. Problem

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

* The copyright in this matter is in BOJ




#. Resolution Process

  1. Read and understand problem

  2. Redefine the problem + abstract

  3. Create solution plan (select Algorithm, Data structure)

  4. Prove the plan (check performance time and usage memory)

  5. Carry out the plan

  6. Look back on the plan and find a way to improve it


#. Solve


생각처럼 잘 안 풀렸던(?) 문제다.

문제가 짧다고 방심하지 말자.. ㅋuㅋ


#. Code


처음으로 접근했던 해결 방법은


(0, 0)부터 출발해서 스위치가 있는 방이라면 스위치를 눌러볼 것인데,

해당 방에 불이 꺼져 있다면 스위치로 불을 켜준다.

새로운 방에 불이 켜졌다면 (0, 0)부터 다시 탐색을 시도하는 방법이었다.


(0, 0)부터 다시 탐색을 시도했던 이유는

ex. (0, 0)에서 이동할 수 없었던 방을 다시 이동할 수 있게 되는 경우가 있었기 때문이다.


하지만 visited 배열을 계속 다시 생성해주어야 했기 때문에

메모리와 시간이 굉장히 비효율적이었다..


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
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 int N, M;
    static int[] dr = { -1, 0, 1, 0 }, dc = { 0, -1, 0, 1 };
    static ArrayList<Point>[][] switchs;
 
    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());
        switchs = new ArrayList[N][N];
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                switchs[i][j] = new ArrayList<>();
            }
        }
        // 스위치 정보
        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;
            int a = Integer.parseInt(st.nextToken()) - 1;
            int b = Integer.parseInt(st.nextToken()) - 1;
            switchs[x][y].add(new Point(a, b));
        }
 
        System.out.println(process());
    }
 
    private static int process() {
 
        boolean[][] visited = new boolean[N][N];
        boolean[][] isLight = new boolean[N][N];
        int cnt = 1;
        // (0, 0)에서 출발
        Queue<Point> q = new LinkedList<>();
        q.add(new Point(0, 0));
        isLight[0][0] = true;
        visited[0][0] = true;
    
        while (!q.isEmpty()) {
            Point now = q.poll();
            
            // 스위치가 있다면 불을 켜보자.
            if(switchs[now.r][now.c].size() > 0) {
                boolean flag = false;
                // 스위치를 눌러볼까?
                for (Point p : switchs[now.r][now.c]) {
                    // 불이 꺼져있는 방이라면
                    if(!isLight[p.r][p.c]) {
                        // 불을 켜고
                        isLight[p.r][p.c] = true;
                        flag = true;
                        cnt++;
                    }
                }
                // (0, 0)부터 다시 출발
                if(flag) {
                    q.clear();
                    q.add(new Point(0, 0));
                    visited = new boolean[N][N];
                    visited[0][0] = true;
                    
                    continue;
                }
            }
            
            // 다음 좌표로 이동
            for (int d = 0; d < 4; d++) {
                int rr = now.r + dr[d];
                int cc = now.c + dc[d];
                // 범위를 넘어갈 경우
                if(rr < 0 || cc < 0 || rr >= N || cc >= N) continue;
                // 이미 방문했거나 불이 꺼져있을 경우
                if(visited[rr][cc] || !isLight[rr][cc]) continue;
 
                visited[rr][cc] = true;
                q.add(new Point(rr, cc));
            }
        }
 
        return cnt;
    }
 
    static class Point {
        int r, c;
 
        public Point(int r, int c) {
            this.r = r;
            this.c = c;
        }
 
    }
 
}
cs



#. Code_v2


조금 더 최적화된 방법이다.


1. 현재 방에서 이동할 수 있는 방을 체크해둔다.

다시 (0, 0)으로 돌아가지 않더라도 언제든 다시 방문해볼 수(시도해볼 수) 있는 상태


2.  현재 방에 스위치가 있다면 눌러보자.

불이 꺼져있는 방이라면 불을 켜주고,

이동할 수 있는 방이라면 queue에 추가해주자.

(여기서 이동할 수 있는 방인지 체크했던 상태를 활용하게 된다.)


3. 이번엔 현재 방에서 이동할 수 있는 방으로 이동해보자.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
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 int[] dr = { -1, 0, 1, 0 }, dc = { 0, -1, 0, 1 };
    static ArrayList<Point>[][] switchs;
 
    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());
        switchs = new ArrayList[N][N];
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                switchs[i][j] = new ArrayList<>();
            }
        }
        // 스위치 정보
        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;
            int a = Integer.parseInt(st.nextToken()) - 1;
            int b = Integer.parseInt(st.nextToken()) - 1;
            
            switchs[x][y].add(new Point(a, b));
        }
 
        System.out.println(process());
    }
 
    private static int process() {
 
        boolean[][] visited = new boolean[N][N]; // 방문한 방
        boolean[][] isLight = new boolean[N][N]; // 불이 켜진 방
        boolean[][] isMove = new boolean[N][N]; // 이동할 수 있는 방
        
        int cnt = 1;
        // (0, 0)에서 출발
        Queue<Point> q = new LinkedList<>();
        q.add(new Point(0, 0));
        isLight[0][0] = true;
        visited[0][0] = true;
    
        while (!q.isEmpty()) {
            Point now = q.poll();
            // 현재 방에서 이동할 수 있는 방 상태를 체크
            for (int d = 0; d < 4; d++) {
                int rr = now.r + dr[d];
                int cc = now.c + dc[d];
                // 범위를 넘어갈 경우
                if(rr < 0 || cc < 0 || rr >= N || cc >= N) continue;
                
                isMove[rr][cc] = true;
            }
            
            // 스위치를 눌러볼까?
            for (Point p : switchs[now.r][now.c]) {
                // 불이 꺼져있는 방이라면
                if(!isLight[p.r][p.c]) {
                    // 불을 켜고
                    isLight[p.r][p.c] = true;
                    cnt++;
                    
                    // 이동할 수 있는 방이라면 queue에 추가
                    if(isMove[p.r][p.c] && !visited[p.r][p.c]) {
                        visited[p.r][p.c] = true;
                        q.add(new Point(p.r, p.c));
                    }
                }
            }
            
            // 현재 위치에서 이동할 수 있는 방으로 이동
            for (int d = 0; d < 4; d++) {
                int rr = now.r + dr[d];
                int cc = now.c + dc[d];
                // 범위를 넘어갈 경우
                if(rr < 0 || cc < 0 || rr >= N || cc >= N) continue;
                // 이미 방문했거나 불이 꺼져있거나 이동할 수 없는 방이라면
                if(visited[rr][cc] || !isLight[rr][cc] || !isMove[rr][cc]) continue;
 
                visited[rr][cc] = true;
                q.add(new Point(rr, cc));
            }
        }
 
        return cnt;
    }
 
    static class Point {
        int r, c;
 
        public Point(int r, int c) {
            this.r = r;
            this.c = c;
        }
 
    }
 
}
 
cs






반응형
저작자표시

'PS > Problem_Solving' 카테고리의 다른 글

[BOJ] 2841. 외계인의 기타 연주(Stack).java  (0) 2020.11.15
[BOJ] 14464.소가 길을 건너간 이유 4(PQ).java  (0) 2020.11.14
[BOJ] 20005.보스몬스터 전리품(BFS).java  (0) 2020.11.11
[BOJ] 3709. 레이저빔은 어디로(DFS).java  (0) 2020.11.11
[BOJ] 2812.크게 만들기(Stack).java  (0) 2020.11.07
댓글
최근에 올라온 글
최근에 달린 댓글
링크
Total
Today
Yesterday
TAG more