[백준/JAVA] 14594번: 동방 프로젝트 (Small)

📖 문제

14594번: 동방 프로젝트 (Small)

 

 

💡  풀이 방식

• 구현, 시뮬레이션

필요 자료구조
- 1부터 N-1까지의 벽 상태를 나타낼 boolean형 배열 (true: 벽 허물어짐 / false: 벽 있음)

 

방이 N개면, 벽의 갯수는 N-1개다.

(예 : O를 동방, |를 벽이라 할 때, O|O|O|O|O ⇒ 동방이 5개면, 벽은 동방-1개인 4개)

그러므로 1~N-1 까지의 벽의 상태를 나타내는 1차원 boolean형 배열을 사용한다.

 

M번 동안 입력받은 x < y에 대해 벽을 허무는 작업을 수행한다.

- 벽을 허물 때는 x부터 y 미만까지 허물어지지 않은 칸(walls[i] == false)에 대해 허물었다는 표시(walls[i] = true)를 한다.

 

1부터 N-1까지 벽의 상태 배열을 돌며, 허물어지지 않은 벽(walls[i] == false)의 갯수를 센다.

동방 수 = 벽의 수 + 1이므로, 허물어지지 않은 벽의 수에 1을 더해 정답으로 출력한다.

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    static int N,M;
    static boolean[] walls; // true: 벽 무너짐, false: 벽 있음
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        
        N = Integer.parseInt(br.readLine());
        M = Integer.parseInt(br.readLine());
        
        walls = new boolean[N];   //1 ~ (N-1)개
        
        while(M --> 0) {
            st = new StringTokenizer(br.readLine(), " ");
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            
            if(x < y) {
                breakWall(x, y);
            }
        }
        
        int cnt = 0;
        for(int i = 1 ; i < N ; i++) {
            if(!walls[i])
                cnt++;
        }
        
        System.out.println(cnt + 1);    // 방 수 = 벽 수 +1
    }
    
    private static void breakWall(int x, int y) {
        for(int i = x ; i < y ; i++) {
            if(!walls[i]) {
                walls[i] = true;
            }
        }
    }
}
 

 

 

 

➕ 다른 풀이 방식

유니온파인드 비슷하게 푸신 풀이라고 합니다...

Baekjoon 14594 동방 프로젝트 (Small) JAVA

---

 

 

1회독	2회독	3회독	4회독	5회독
V