[백준] 14939번 불 끄기 (Python,파이썬)

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

14939번: 불 끄기

 

24/02/07 현재 난이도: 플레 4

쓰이는 알고리즘: 그리디, 브루트포스

남의 도움을 받았는가? O

 

 

 

서론

 

이 문제는 icpc 신촌 겨울캠프에서 수업도중 나온 문제이다.

그 때 자세한 풀이를 하지는 않았지만 강사님이 y축 2번째줄 부터 돈다고 생각한다면

y축 1번째줄 바로위가 켜져있으면 그걸 꺼 줄 수 있는 방법이 2번째줄 그 x칸을 눌러주는것

말고는 없다. 두번 이상 같은 버튼을 누르는 것은 의미가 없다. 라는 힌트를 받고

 

수업이 끝난 후 문제를 풀어봤다.

 

이 문제를 총 16번만에 맞췄는데 맞추고 나서 다른 분들 코드를 보니 나보다 훨씬 간단했다.

하지만 그것은 내가 실전에서 쓸 수 있는 코드는 아니었고 나의 코드는 120줄이다.

그래서 그 코드를 다 일일히 설명하기 보다는 나의 알고리즘을 적어보려고 한다.

 

사실 이 16번째 정답에 오기까지 100줄 이상의 코드도 짜보고 했으나 계속해서 실수 또는

구현에서 오류가 나서 계속 코드를 적는 것을 반복했다.

 

본론으로 들어가서 문제에 대해 이야기해보면

 

나의 알고리즘은 처음에는 강사님이 힌트를 주신 데로 생각했다 아 두 번째 줄부터 돌면서

1번째줄이 켜져있으면 바로 x축은 같고 y축은 1큰 곳을 눌러주면 되겠구나 싶었다

(예를 들면 (1,1)<<(x,y) 이 켜져있다면 (1,2) 를 무조건 눌러야 하는것이다. 왜냐하면 (1,1)은 (2,1)에서 눌러주지 않으면 앞으로도 절대 꺼질 수 없기 때문이다.)

 

그렇게 코드를 짜면 이 문제에서 나온 테스트 케이스는 문제없이 답이 맞게 나온다.

이대로 제출 했더니 바로 틀렸습니다를 받아버렸다.

 

그래서 나는 왜 틀렸나 고민하다가 아 y의 첫 번째 줄을 눌려 줄 수도 있구나! 라는 것을 깨달아 버렸다.

하지만 y의 첫 번째줄을 누르는 경우의 수는 2**10 즉 1024가지 이다.

하지만 10*10 짜리 그래프이기때문에 1024배정도는 딱히 신경쓰일 정도는 아니었다.

그래서 나는 이 1024개를 어떻게 표현해줄까를 고민하다 from itertools import combinations 라는

라이브러리가 기억이 났다 (아마 1학년 2학기 초급스터디때 들었던 내용인것 같다.)

이 라이브러리를 사용하면 모든 조합을 다 표현해 줄 수 있다.

그래서 위에 칸 10개를 모든 조합으로 껏다켰다 해주며 만약에 불이 다 꺼진다면 답에 1을 더하는 형식으로

답을 구해주고 그 답을 dapli라는 곳에 넣어서 만약 dapli가 비어있지 않다면 min값을 출력하고 그렇지 않으면

-1을 출력하게끔 해줬다.

 

위에 내가 설명한 것보다 나의 코드가 더길다.. 일단 올려보겠다

import copy
from itertools import combinations

dapli=[]
graph=[[False for _ in range(10)] for _ in range(10)]
top=[0,1,2,3,4,5,6,7,8,9]
for y in range(10):
    li=list(input())
    for x in range(10):
        if li[x]=='O':
            graph[y][x]=True

for i in range(11):
    tup=list(combinations(top,i))
    if i==0:
        graph2=copy.deepcopy(graph)
        dap=0
        for y1 in range(1,10):
            for x1 in range(10):
                if graph2[y1-1][x1]:
                    dap+=1
                    graph2[y1-1][x1]=False
                    if graph2[y1][x1]:
                        graph2[y1][x1]=False
                    else:
                        graph2[y1][x1]=True
                    if x1>0:
                        if graph2[y1][x1-1]:
                            graph2[y1][x1-1]=False
                        else:
                            graph2[y1][x1-1]=True
                    if y1<9:
                        if graph2[y1+1][x1]:
                            graph2[y1+1][x1]=False
                        else:
                            graph2[y1+1][x1]=True
                    if x1<9:
                        if graph2[y1][x1+1]:
                            graph2[y1][x1+1]=False
                        else:
                            graph2[y1][x1+1]=True
            pandan=1
            for hu in range(10):
                for yu in range(10):
                    if graph2[hu][yu]:
                        pandan=0
            if pandan:
                dapli.append(dap)
                            
                    
        
    else:
        for x in tup:
            graph2=copy.deepcopy(graph)
            dap=0
            for y in x:
                dap+=1
                if graph2[0][y]:
                    graph2[0][y]=False
                else:
                    graph2[0][y]=True
                if graph2[1][y]:
                    graph2[1][y]=False
                else:
                    graph2[1][y]=True
                if y>=1:
                    if graph2[0][y-1]:
                        graph2[0][y-1]=False
                    else:
                        graph2[0][y-1]=True
                if y<9:
                    if graph2[0][y+1]:
                        graph2[0][y+1]=False
                    else:
                        graph2[0][y+1]=True
            
            for y1 in range(1,10):
                for x1 in range(10):
                    if graph2[y1-1][x1]:
                        dap+=1
                        graph2[y1-1][x1]=False
                        if graph2[y1][x1]:
                            graph2[y1][x1]=False
                        else:
                            graph2[y1][x1]=True
                        if x1>0:
                            if graph2[y1][x1-1]:
                                graph2[y1][x1-1]=False
                            else:
                                graph2[y1][x1-1]=True
                        if y1<9:
                            if graph2[y1+1][x1]:
                                graph2[y1+1][x1]=False
                            else:
                                graph2[y1+1][x1]=True
                        if x1<9:
                            if graph2[y1][x1+1]:
                                graph2[y1][x1+1]=False
                            else:
                                graph2[y1][x1+1]=True
            pandan=1
            for hu in range(10):
                for ku in range(10):
                    if graph2[hu][ku]==True:
                        pandan=0
            if pandan:
                dapli.append(dap)
                
                                
        
    
if dapli:
    print(min(dapli))
else:
    print(-1)

 

 

풀이가 약 120줄 정도 되는데 사실 이것은 내가 위에 써놓은 말을 구현 해놓은 것이다.

말은 짧았지만 구현은 길다...

 

 

마지막으로.. 나한테 이 문제 구현이 쉽지 않았다.

내가 짠 알고리즘을 코드로 표현한다는게  생각보다 쉽지 않았다.

무려 알고리즘을 제대로 세운후 12번이나 틀렸다...

 

알고리즘을 생각하는 능력과 구현능력 모두 증진되길 바라며 여기서 포스팅을 마치겠다.