[BOJ] 2138번: 전구와 스위치 (Greedy)

728x90

 

 

<<다시 풀어보기>>

 

문제 링크

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

 

 

 

 

TIL

  • 그리디 알고리즘이지만, 무작정 푸는 것이 아닌 경우의 수를 나눠서 각 경우의 수를 그리디 돌려야하는 문제 !! 
    • 이런 문제 유형도 있으니 항상 고려하기
  • 1 <> 0 반전하는 쉬운 방법
    • value = 1-value 하면 됨 ( https://taltal.tistory.com/100 참고 )
    • 혹은 XOR 연산으로 가능 (^) 
    • 혹은 NOT 연산으로 가능 (not) > 대신 bool 타입으로 바뀜
  • 시간 초과에 대해서 
  • 종료 조건을 어떻게 설정하지 ? > 불가능하면 -1을 반환해야함
    • 다 돌고나서도 타겟 상태와 다르다면 -1을, 아니라면 cnt를 반환
  • 왜 그리디 알고리즘을 사용하는 것이 적합한가?
    • 전구를 스위치하는 순서는 중요하지 않음 !!! 누르냐 아니냐 여부가 중요
    • 로컬 최적해가 글로벌 최적해를 보장: 전구의 현재 상태가 목표 상태와 다를 때 스위치를 눌러 상태를 변경하는 것이 그 순간에서 최선의 행동입니다. 이 결정은 그 이후의 전구들에게 영향을 미치지만, 순차적으로 스위치를 처리함으로써 최종적으로 원하는 결과를 얻을 수 있습니다.
    • 뒤돌아갈 필요가 없음: 한 번 스위치를 누른 이후에는, 해당 스위치를 다시 고려할 필요가 없습니다. 이는 각 스위치의 누름이 그 이후의 전구들에 대한 결정에만 영향을 미친다는 사실 때문입니다. 즉, 한 번 결정이 내려지면, 그 결정은 최종적으로 전체 문제 해결에 기여합니다.
    • 문제의 독립성: 각 스위치를 누르는 결정은 그 순간의 전구 상태에만 기반하고 있으며, 각 결정은 서로 독립적으로 최적의 선택을 제공합니다. 이는 전체 문제를 더 작은 문제로 나누고 각각을 독립적으로 해결할 수 있음을 의미합니다.
    • 연쇄 효과: 스위치를 누르는 행위는 연속된 세 전구에 영향을 미치며, 이러한 연쇄 효과를 고려하여 각 스위치를 누를지 말지 결정합니다. 스위치를 누름으로써 발생하는 연쇄적인 상태 변화를 계산에 포함시키는 것이 그리디 알고리즘의 핵심입니다.
  • 스위치를 왜 한 번만 누른다고 가정하는가?
    • 한 개의 스위치를 여러 번 누를 수 있지만, 실제로는 그렇게 할 필요가 없습니다. 스위치를 한 번 누르면 연결된 전구들의 상태가 반전됩니다. 같은 스위치를 두 번 누르면 전구들의 상태가 원래대로 돌아오기 때문에, 스위치를 두 번 누른 효과는 아무 것도 하지 않은 것과 같습니다. 이러한 이유로, 각 스위치를 최대 한 번만 누르는 것을 고려하면 충분합니다.
# BFS -> 최소 횟수
# 이 문제는 BFS가 아니라 그리디 사용해야함!!!!

n = int(input())

current = list(map(int, list(input())))
will = list(map(int, list(input())))

def click(c_grid, i):
    global n
    temp = c_grid.copy()    # 필수 !!!! 안하면 c_grid가 그대로 수정됨
    for bulb in (i-1, i, i+1):
        if 0<=bulb<n:
            temp[bulb] = not temp[bulb]
    return temp

def find_first():
    global current
    global will
    for i in range(n):
        if current[i] != will[i]:
            return i
        
def solve():
    cnt = 0
    while True:
        if current == will:
            print(cnt)
            break

        i = find_first()
        for bulb in (i, i+1, i+2):  # click
            if 0<=bulb<n:
                current[bulb] = not current[bulb]
            cnt += 1
    return cnt

if __name__=="__main__":
    solve()

 

[ 문제 풀이 방법 ] - Greedy 참고 !!!

  • 하나의 버튼을 누르면 양옆에 모두 영향을 받기 때문에 이를 고려해야 함
    • 따라서 i-1번째 상태를 기준으로 하고, 이를 바꾸기 위해 i번째 스위치를 누르도록 동작 실행
    • 즉, 1번째 전구는 누르거나 누르지 않거나로 나뉘게 됨
  • 1번째를 누르지 않고 전체 전구를 순회한 뒤 답이 나오면 그대로 반환
  • 답이 나오지 않는다면 1번째를 누르고 다시 전체 전구를 순회하는 방법으로 한 번 더 실행
  • 이때 중요한 거 !!!!!!! 배열을 복사해두고 사용해야 함 >> 그렇지 않으면 초기화 불가능
  • 1번째를 누르지 않고 전구 순회한 뒤에 답이 아니면 1번 누르는 거로 해도 되지 않나? >> 내 처음 생각
    • 1번째를 누르면 2번째 전구에도 영향이 가고, 그러면 그 뒤에 누르는 조합이 바뀔 수도 있으므로 아예 달라짐
  • 첫 번째 전구를 누른다면 cnt +1 해줘야 함 !!!!

 

 

Code

n = int(input())
bulbs = list(map(int,list(input())))
target = list(map(int,list(input())))

def press_first(current):
    cnt = 0
    if target==current:
        return cnt
    
    for i in range(1,n):
        if current[i-1] != target[i-1]:
            click(i)
            cnt += 1
    return cnt if target == current else -1

def press_second(current):
    cnt = 0
    if target==current:
        return cnt
    cnt += 1
    current[0] = 1-current[0]
    current[1] = 1- current[1]
    
    for i in range(1,n):
        if current[i-1] != target[i-1]:
            click(i)
            cnt += 1
    return cnt if target == current else -1

def click(i):
    if i==0:
        current[0] = 1-current[0]
        current[1] = 1- current[1]
    elif i==n-1:
        current[i] = 1- current[i]
        current[i-1] = 1- current[i-1]
    else:
        current[i] = 1-current[i]
        current[i-1] = 1-current[i-1]
        current[i+1] = 1-current[i+1]

if __name__ == "__main__":
    current = bulbs.copy()
    ans = press_first(current)
    if ans > 0:
        print(ans)
    else:
        current = bulbs.copy()
        print(press_second(current))