[백준/JAVA] 16960번: 스위치와 램프

📖 문제

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

 

 

 

💡  풀이 방식

• 구현

필요 자료구조
- 램프 갯수 저장용, 크기가 M+1인 int형 배열
- 램프 정보 저장 리스트 배열

 

1. 각 스위치에 몰린 램프 정보를 저장한다.

for(int i = 1 ; i <= N ; i++) {
    st = new StringTokenizer(br.readLine(), " ");
    int x = Integer.parseInt(st.nextToken());

    while(x --> 0) {
        int tmp = Integer.parseInt(st.nextToken());
        list[i].add(tmp);
        arr[tmp]++;
    }
}

 

 

 

2. 스위치 수만큼 반복문을 돌면서, 각각의 스위치에 몰린 램프의 idx 값을 배열에서 하나씩 빼본다.

그러면서 유지가 되는지/아닌지 flag 변수로 판단한다.

boolean flag = true;
        
// 하나씩 빼면서 유지되는지 확인하기
for(int x : list[idx]) {
    arr[x]--;

    if(arr[x] <= 0) {
        flag = false;
    }
}

 

 

 

3. 확인 후에는 뺀 값들을 원상복구한다.

for(int x : list[idx]) {
    arr[x]++;
}

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    static int N,M;
    static int[] arr;               // 램프 갯수 배열
    static List<Integer>[] list;    // 램프 정보 저장 리스트
    
    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());
        
        arr = new int[M+1];
        list = new ArrayList[N+1];
        for(int i = 1 ; i <= N ; i++) {
            list[i] = new ArrayList<>();
        }
        
        for(int i = 1 ; i <= N ; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            int x = Integer.parseInt(st.nextToken());
            
            while(x --> 0) {
                int tmp = Integer.parseInt(st.nextToken());
                list[i].add(tmp);
                arr[tmp]++;
            }
        }
        
        for(int i = 1 ; i <= N ; i++) {
            if(isPossible(i)) {
                System.out.println(1);
                return;
            }
        }
        System.out.println(0);
    }
    
    // 모든 램프 켤 수 있는지 확인하는 메소드
    private static boolean isPossible(int idx) {
        boolean flag = true;
        
        // 하나씩 빼면서 유지되는지 확인하기
        for(int x : list[idx]) {
            arr[x]--;
            
            if(arr[x] <= 0) {
                flag = false;
            }
        }
        
        // 확인한 값 원상복구하기기
        for(int x : list[idx]) {
            arr[x]++;
        }
        
        return flag;
    }
}

 

 

---

💦 어려웠던 점

- 1차원 배열 리스트 사용할 생각을 못 했다.

- isPossible 함수에서 flag 변수를 사용하지 않고 바로 return false 처리하면 58%에서 틀린다.. (값 원상복구를 안 해서 그런듯)

 

 

 

 

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

---

(참고)

[ 백준 16960 ] 스위치와 램프