전구와 스위치[백준 2138] - python

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

2138번: 전구와 스위치

 

1년 전에 풀때 못풀었던 문제다. 

이번에 풀게되었는데 이번에도 실패다. (고마워요 다른 블로거 포스팅들) 다음엔 꼭 성공하리...

다음에 실패하지 않기 위해 이번에는 생각을 정리해서 글을 남겨둘 거다.

다음에 풀 나에게 힌트가 되기를 바라며...

 

정답 코드 먼저!!!

 

n = input()
first = list(input())
target = list(input())

def change_zero_index(light) :
  count = 1
  light[0] = str(1 - int(light[0]))
  light[1] = str(1 - int(light[1]))

  for i in range(1, len(light)) :
    if target[i-1] != light[i-1] :
      count += 1
      light[i-1] = str(1 - int(light[i-1]))
      light[i] = str(1 - int(light[i]))
      if i != int(n) - 1 :
        light[i+1] = str(1 - int(light[i+1]))

  if light == target:
      return count

  
  return 100001

def not_change_zero_index(light) :
  count = 0
  
  for i in range(1, len(light)):
    if target[i-1] != light[i-1]:
      count += 1
      light[i-1] = str(1 - int(light[i-1]))
      light[i] = str(1 - int(light[i]))

      if i != int(n) - 1:
        light[i+1] = str(1 - int(light[i+1]))

  if light == target:
      return count

  return 100001

answer_first = change_zero_index(first[:])
answer_second = not_change_zero_index(first[:])
answer = min(answer_first, answer_second)

if answer == 100001 :
  print(-1)
else :
  print(answer)

 

접근방법 

1. 첫번째 전구를 토글하고 접근하는 것과 토글하지 않고 접근하는 경우로 케이스를 나눠서 계산한다. 
   => 첫번째 전구는 비교할 이전의 전구 상태가 존재하지 않는다. 그래서 두개의 경우로 나누어서 접근
2. 순회하면서 이전의 전구 상태와 바꿔야 하는 상태를 비교하고 토글여부를 결정한다.
   =>  이전 전구의 상태를 비교하면서 순회하면 결국 현재 전구도 비교하게 될 것이다.
3. 이전에 지나온 전구는 건드리지 않는다.
   => 이전의 전구를 건드리면 다시 그 이전으로 돌아가야 하고 이렇게 되면 제일 처음의 과정을 반복하게 된다. 메모리 초과나 시간 초과에 걸릴 것이다.

(대체 이런개념을 제한 시간안에 어떻게 떠올리는거지....)

 

 

메모리 초과로 실패했던 이전의 코드

 

def toggle_item(x) :
  if x == '1' :
    return '0'
  return '1'

def toggle(s, i) :
  s = list(s)
  
  if i == 0 :
    s[:2] = list(map(toggle_item, s[:2]))
  elif i == len(s) :
    s[i-2:] = list(map(toggle_item, s[i-2:]))
  else :
    s[i-1:i+2] = list(map(toggle_item, s[i-1:i+2]))
  return ''.join(s) 

n = input()
first = input()
second = input()

# bfs
bfs = []
result_list = {}
result_list[first] = 0
bfs.append([first, 0])

while True :
  if len(bfs) == 0:
    break
  
  target, count = bfs.pop(0)
  
  if target == second :
    break
  for i in range(len(target)) :
    toggle_target = toggle(target, i)
    if toggle_target in result_list :
      result_list[toggle_target] = min(result_list[toggle_target], count+1)
    else :
      result_list[toggle_target] = count+1
    bfs.append([toggle_target, count+1])

if second in result_list :
  print(result_list[second])
else :
  print(-1)

 

bfs로 접근하려 했었고 테스트 케이스만 통과했었고 반례 넣어보면서 탈출조건을 세부화 하려 했으나 메모리 초과로 실패해버렸다.