[PS] 14939) 불끄기

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

14939번: 불 끄기

Platinum5) 14939.불끄기

 

• 그리디 알고리즘, 브루트포스 알고리즘, 비트마스킹, 구현

 

S사 코딩테스트 이후 간만에 푼 구현 문제.

이번 문제도 길이가 짧고 요구사항도 간단하다. 주어진 10*10 필드에 0과 1로 전구가 켜져있거나 꺼져있는데 switch를 작동해서 이를 다 끄도록 해야한다. swtich는 해당 좌표를 누를 시 상하좌우와 함께 상태가 변한다. 이때 최소의 스위치로 모두 끄는 것이 관건.

 

구현은 간단하고 풀이도 어렵지 않다. 핵심 풀이는 브루트포스 알고리즘. 하지만 모든 점의 경우의 수를 다 나눠보면 2^100이기 때문에 살짝 줄여줘야한다. 전구는 상하좌우가 함께 꺼지는 것을 고려하여 맨 윗줄에서만 어떤 전구를 스위치할지 브루트포스로 탐색하고 나머지는 상위 전구를 사용해서 누르도록 풀이하면 된다. 상위 코드로 작성하면 맨 윗줄에서 총

10C0+10C1+...+10C10 으로 1024번의 경우의 수가 있으며 해당 경우의 수마다 총 100개의 점에 접근하므로 총 10번 정도의 코드가 수행된다.

 

풀이 코드 구현은 다음과 같다.

import sys
    import copy
    from itertools import combinations
    input = sys.stdin.readline

    dx = [0, 0, 1, -1]
    dy = [1, -1, 0, 0]

import와 상하좌우 좌표에 접근할 direction을 설정했다.

def getdata():
        board = list()
        for i in range(10) :
            board.append(list(input()))
            board[i].pop()
        return board

    def printboard(board) :
        for i in range(10) :
            print(board[i])

데이터를 받을 getdata함수와 디버깅 시 좀 더 편하게 확인하기 위한 print함수이다.

def switch(board, x, y) :
        if board[x][y] == '#' :
            board[x][y] = 'O'
        else :
            board[x][y] = '#'
        for i in range(4) :
            nx = x+dx[i]
            ny = y+dy[i]
            if 0<=nx<10 and 0<=ny<10 :
                if board[nx][ny] == '#' :
                    board[nx][ny] = 'O'
                else :
                    board[nx][ny] = '#'
        return board

해당 보드에서 x,y점의 스위치를 누르는 행동의 함수이다. 상하좌우 좌표에 접근하고 범위 안에 존재하면 상태를 변환한다.

def sol(board) :
        minval = 1000
        for i in range(1, 11) :
            for choice in combinations([k for k in range(10)], i) :
                copy_board = copy.deepcopy(board)
                cnt, flag = 0, 0
                for j in choice :
                    copy_board = switch(copy_board, 0, j)
                    cnt += 1
                for l in range(1,10) :
                    for m in range(10) :
                        if copy_board[l-1][m] == 'O' :
                            copy_board = switch(copy_board, l, m)
                            cnt += 1
                for n in range(10) :
                    if copy_board[9][n] == "O" :
                        flag = 1
                        break
                if flag == 0 :
                    if cnt < minval :
                        minval = cnt
                    # print(choice)
                    # print(flag, cnt, minval)
                    # printboard(copy_board)

solution함수이다. 위에서 언급한 것처럼 combinations함수를 이용하여 첫줄의 모든 경우의 수를 구하고 해당 경우마다 2번 째 줄부터 접근하여 상위 전구를 확인하고 스위치해준다. 이후 마지막 줄에 켜진 전구가 있으면 flag를 통해 컨트롤하여 해당 경우는 제외한다.