[백준, Java] 14939번, 불 끄기, (완전 탐색, 그리드)

문제 링크

14939번: 불 끄기

전구 100개가 10 x 10 정사각형 모양으로 늘어서 있다. 전구에 달린 스위치를 누르면 그 전구와 위, 아래, 왼쪽, 오른쪽에 있는 전구의 상태도 바뀐다. 전구 100개의 ..

www.acmicpc.net

주의사항

JAVA를 사용하여 프로그램을 사용하였습니다.
백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

문제 설명

접근 방법

이 문제에 핵심

1. 전구는 10 x 10 정사각형 모양으로 늘어져 있습니다.

2. 전구를 ON/OFF할 수 있으며, 상태를 바꾸면 상하좌우도 영향을 받습니다.

3. 모든 전구를 끄기 위해 전구의 상태를 바꿔야 하는 최소 횟수를 결과로 출력합니다.

4. 모두 끄는 것이 불가능하면 -1을 결과로 출력합니다.

알고리즘 진행 순서.

1. 입력된 정보를 저장합니다.

2. 좌상단부터 불끄기를 진행하며 전구를 모두 끄는 최소 횟수를 탐색합니다.

3. 탐색을 통해 최소 횟수를 결과로 출력합니다.

전구 상태 변경하기(그리드)

전구를 상태를 바꾸면 상하좌우 영향을 받게 됩니다.

	X
X	X	X
	X

최상단부터 전구 상태를 변경하는 것을 순서대로 진행한다면

#	#	#	#	#
#	#	#	#	#
#	#	#	#	#

2번째 줄에 대해서 전구 상태 변경이 종료되었을 때에는 1번째 줄에는 모든 전구가 꺼져있어야 합니다.

Why?

더 이상 1, 2번째 전구의 상태를 변경하지 않을 것이기 때문에, 1번째 전구는 상태 변경이 더 이상 일어나지 않을 것이기 때문입니다.

만약, 2번째 줄을 상태 변경이 진행되었을 때 아래와 같으면

#	#	#	O	#
#	#	#	#	#
#	#	#	#	#

1번째 줄에 전구가 켜진 상태가 존재하므로 해당 방법으로는 모든 전구를 끌 수 없습니다.

즉, 해당 방법에 대해서 탐색을 중단하고 다른 방법으로 전구를 끄는 법을 탐색합니다.(그리드)

각 행 전구 상태 변화(완전 탐색)

각 행에 대해서 상태 변화를 탐색하기 위해서 완전 탐색을 진행하였습니다.

전구는 10개로 고정되어 있기 때문에 조합을 찾아도 2^10(1024)개로 탐색이 가능합니다.

※예제 입력을 푸는 과정을 확인하시면 이해하기 편하실 것입니다.

예제입력 1.

1. 입력된 정보를 저장합니다.

[전구]

#	O	#	#	#	#	#	#	#	#
O	O	O	#	#	#	#	#	#	#
#	O	#	#	#	#	#	#	#	#
#	#	#	#	O	O	#	#	#	#
#	#	#	O	#	#	O	#	#	#
#	#	#	#	O	O	#	#	#	#
#	#	#	#	#	#	#	#	#	#
#	#	#	#	#	#	#	#	O	#
#	#	#	#	#	#	#	O	O	O
#	#	#	#	#	#	#	#	O	#

2. 좌상단부터 불끄기를 진행하며 전구를 모두 끄는 최소 횟수를 탐색합니다.

※ 정답이 되는 경우로 진행하겠습니다.

1행 전구 상태 변경 {}

#	O	#	#	#	#	#	#	#	#
O	O	O	#	#	#	#	#	#	#
#	O	#	#	#	#	#	#	#	#
#	#	#	#	O	O	#	#	#	#
#	#	#	O	#	#	O	#	#	#
#	#	#	#	O	O	#	#	#	#
#	#	#	#	#	#	#	#	#	#
#	#	#	#	#	#	#	#	O	#
#	#	#	#	#	#	#	O	O	O
#	#	#	#	#	#	#	#	O	#

2행 전구 상태 변경 { 2 }

#	#	#	#	#	#	#	#	#	#
#	#	#	#	#	#	#	#	#	#
#	#	#	#	#	#	#	#	#	#
#	#	#	#	O	O	#	#	#	#
#	#	#	O	#	#	O	#	#	#
#	#	#	#	O	O	#	#	#	#
#	#	#	#	#	#	#	#	#	#
#	#	#	#	#	#	#	#	O	#
#	#	#	#	#	#	#	O	O	O
#	#	#	#	#	#	#	#	O	#

2번째 줄 전구 상태 변경이 완료되었으므로, 1번째 줄 전구가 모두 상태가 꺼져있는데 확인합니다.

→ 모두 꺼져있기 때문에 3번째 줄 전구 상태 변경에 대해서 탐색이 가능합니다.

3행 전구 상태 변경 {}

#	#	#	#	#	#	#	#	#	#
#	#	#	#	#	#	#	#	#	#
#	#	#	#	#	#	#	#	#	#
#	#	#	#	O	O	#	#	#	#
#	#	#	O	#	#	O	#	#	#
#	#	#	#	O	O	#	#	#	#
#	#	#	#	#	#	#	#	#	#
#	#	#	#	#	#	#	#	O	#
#	#	#	#	#	#	#	O	O	O
#	#	#	#	#	#	#	#	O	#

3번째 줄 전구 상태 변경이 완료되었으므로, 2번째 줄 전구가 모두 상태가 꺼져있는데 확인합니다.

→ 모두 꺼져있기 때문에 4번째 줄 전구 상태 변경에 대해서 탐색이 가능합니다.

4행 전구 상태 변경 {}

#	#	#	#	#	#	#	#	#	#
#	#	#	#	#	#	#	#	#	#
#	#	#	#	#	#	#	#	#	#
#	#	#	#	O	O	#	#	#	#
#	#	#	O	#	#	O	#	#	#
#	#	#	#	O	O	#	#	#	#
#	#	#	#	#	#	#	#	#	#
#	#	#	#	#	#	#	#	O	#
#	#	#	#	#	#	#	O	O	O
#	#	#	#	#	#	#	#	O	#

4번째 줄 전구 상태 변경이 완료되었으므로, 3번째 줄 전구가 모두 상태가 꺼져있는데 확인합니다.

→ 모두 꺼져있기 때문에 5번째 줄 전구 상태 변경에 대해서 탐색이 가능합니다.

5행 전구 상태 변경 { 5, 6 }

#	#	#	#	#	#	#	#	#	#
#	#	#	#	#	#	#	#	#	#
#	#	#	#	#	#	#	#	#	#
#	#	#	#	#	#	#	#	#	#
#	#	#	#	#	#	#	#	#	#
#	#	#	#	#	#	#	#	#	#
#	#	#	#	#	#	#	#	#	#
#	#	#	#	#	#	#	#	O	#
#	#	#	#	#	#	#	O	O	O
#	#	#	#	#	#	#	#	O	#

5번째 줄 전구 상태 변경이 완료되었으므로, 4번째 줄 전구가 모두 상태가 꺼져있는데 확인합니다.

→ 모두 꺼져있기 때문에 6번째 줄 전구 상태 변경에 대해서 탐색이 가능합니다.

....

10행 전구 상태 변경 { }

#	#	#	#	#	#	#	#	#	#
#	#	#	#	#	#	#	#	#	#
#	#	#	#	#	#	#	#	#	#
#	#	#	#	#	#	#	#	#	#
#	#	#	#	#	#	#	#	#	#
#	#	#	#	#	#	#	#	#	#
#	#	#	#	#	#	#	#	#	#
#	#	#	#	#	#	#	#	#	#
#	#	#	#	#	#	#	#	#	#
#	#	#	#	#	#	#	#	#	#

3. 탐색을 통해 최소 횟수를 결과로 출력합니다.

2행 : 2번째

5행 : 5, 6번째

9행 : 9번째

전구 상태를 변경하였을 때 모든 전구가 꺼져있는 상태의 최소값 횟수가 됩니다.

4 결과로 출력합니다.

BufferedReader를 사용하여 입력되는 정보를 저장합니다.
전구 정보를 기준으로 search함수를 통해 전구를 모두 끄는 최소 횟수를 탐색합니다.
탐색을 통해 얻은 최소 횟수를 Bufferedwriter 저장합니다.
BufferedWriter에 저장된 결과를 출력합니다.

search함수는 재귀를 통해서 각 전구 상태 변경을 진행합니다.
search함수는 행에 대해서 상태 변경이 완료되면 N-1행에 전구를 check를 이용하여 확인합니다.
check함수는 행에 모든 전구가 꺼져있는지 확인합니다.
inSwitch함수는 상태를 변경하려는 전구가 존재하는지 확인합니다.
onOff함수는 현재 전구 및 상하좌우 인접한 전구에 상태를 변경하는 함수입니다.

결과코드

import java.io.*;
import java.util.*;

public class Main {
    //모든 전구가 꺼져있을 때 전구 상태 변경하는 최소 횟수
    static int result = Integer.MAX_VALUE;
    //전구 정보
    static boolean[][] switches;
    //상하좌우 y, x 변경값
    static int[] dy = {-1, 1, 0, 0};
    static int[] dx = {0, 0, -1, 1};
    public static void main(String[] args) throws IOException {
        //입력값 처리하는 BufferedReader
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //결과값 출력하는 BufferedWriter
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        switches = new boolean[11][11];
        //전구 정보 저장 true : OFF, false : ON
        for(int i=1;i<=10;i++){
            String input = br.readLine();
            for(int j=1;j<=10;j++){
                switches[i][j] = input.charAt(j-1) == '#';
            }
        }
        //1 ~ 10행 전구 상태 변경에 대한 최소 횟수 구하기.
        search(1, 1, 0);
        //모두 끌 수 있는 상태로 만들 수 없을 때
        if(result == Integer.MAX_VALUE){
            result = -1;
        }
        //최소 횟수 BufferedWriter 저장
        bw.write(String.valueOf(result));
        bw.flush();		//결과 출력
        bw.close();
        br.close();
    }
    //1 ~ 10행에 대해서 재귀를 통한 완전 탐색 진행
    static void search(int y, int x, int cnt){
        //최소 횟수보다 전구 킨 횟수가 많을 때
        if(cnt >= result){
            return;
        }

        //행을 모두 탐색했을 때
        if(x == 1){
            //N-1번째 행에 전구가 모두 꺼져있는지 확인
            if(!check(y)){
                return;
            }
        }

        //모든 전구에 대해서 탐색이 끝났을 때
        if(y == 11){
            if(check(12)){
                result = Math.min(result, cnt);
            }
            return;
        }
        //다음 탐색할 전구
        int nxtY = y;
        int nxtX = x + 1;
        if(nxtX == 11){
            nxtY++;
            nxtX = 1;
        }

        //현재 전구의 상태를 변경하였을 때
        if(!switches[y-1][x]){
            onOff(y, x);
            search(nxtY, nxtX, cnt+1);
            onOff(y, x);
        }
        //현재 전구의 상태를 변경하지 않았을 때
        search(nxtY, nxtX, cnt);
    }
    //현재 전구와 상하좌우 인접한 전구의 상태를 변화시키는 함수
    static void onOff(int y, int x){
        switches[y][x] = !switches[y][x]; //현재 전구 상태 변경
        //상하좌우 인접한 전구 상태 변경
        for(int i=0;i<4;i++){
            int ny = y + dy[i];
            int nx = x + dx[i];
            if(inSwitch(ny, nx)){
                switches[ny][nx] = !switches[ny][nx];
            }
        }
    }
    //각 행이 모두 꺼져있는지 확인하는 함수
    static boolean check(int y){
        if(y <= 2){
            return true;
        }
        int preY = y - 2;
        for(int i=1;i<=10;i++) {
            if (!switches[preY][i]) {
                return false;
            }
        }
        return true;
    }
    //변경하려는 전구가 존재하는지 확인하는 함수
    static boolean inSwitch(int y, int x){
        if(y >= 1 && y <= 10 && x >= 1 && x <= 10){
            return true;
        }
        return false;
    }
}

저작자표시

'백준' 카테고리의 다른 글

[백준, Java] 19590번, 비드맨, (그리디) (0)	2024.05.26
[백준, Java] 1023번, 괄호 문자열, (조합, 다이나믹 프로그래밍) (0)	2024.05.14
[백준, Java] 21818번, Do You Know Your ABCs?, (완전 탐색) (0)	2024.05.06
[백준, Java] 17240번, Team Selection, (그리드) (0)	2024.05.06
[백준, Java] 1256번, 사전, (조합, 다이나믹 프로그래밍) (0)	2024.04.30

찬형이의 공부방

[백준, Java] 14939번, 불 끄기, (완전 탐색, 그리드)

문제 링크

주의사항

문제 설명