Intro

• 코딩테스트 단골인 dfs/bfs 를 공부해보았습니다.
• dfs/bfs를 활용하여 지도에서 이동한다거나 하는 node가 구체화 되어 있는 상황은 풀이할만하지만 node를 구체적으로 정하기 어려운 다른상황에서 풀이에 어려움을 겪어서 어려웠던 문제를 정리해보았습니다.

Contents

백준 2666 벽장문의 이동

import sys


Input = sys.stdin.readline

N = int(Input())

door1, door2 = map(int, Input().split())

M = int(Input())
pos = [int(Input()) for _ in range(M)]


cnt = 0 # index, door1, door2까지 '몇 번 문을 움직였는가'
path = [-1] * M # 각 index문 마다 얼마나 이동시켰는가?
ans = 213456789000 # 답(cnt의 최솟값)
def dfs(index, door1, door2):
    #index : 이번에 열 문의 번째, door1,door2 : 지금 문이 위치한 곳
    global cnt, ans
    # 2. 기저조건 (끝낼 조건)
    if ans < cnt: # 현재 최고기록보다 커지면 가망이 없으므로 그만
        return
    if index >= M: # index+1이 들어왔는데 그게 주어진 갯수를 넘으면 중지
        ans = min(ans, cnt)
        return

    # 1. now -> next 구조 잡기
    cnt += abs(door1 - pos[index])
    path[index] = abs(door1 - pos[index])
    dfs(index + 1, pos[index], door2) # door1으로 pos[index]를 여는 경우
    # door1을 pos[index]로 옮겨서 진행하는 모든 방법을 진행
    path[index] = -1
    cnt -= abs(door1 - pos[index]) # 기록 복구

    cnt += abs(door2 - pos[index])
    path[index] = abs(door2 - pos[index])
    dfs(index + 1, door1, pos[index]) # door2으로 pos[index]를 여는 경우
    path[index] = -1
    cnt -= abs(door2 - pos[index]) # 기록 복구
    pass

dfs(0, door1, door2)
print(ans)

풀이

• dfs내부에는 왼쪽문으로 여는 경우와 오른쪽문으로 여는 경우가 존재합니다.

• path 를 통해 각 벽장마다 몇번 움직였는지 체크합니다.

• 처음에 dfs(0, door1, door2) 로 시작합니다.

  • path와 cnt를 업데이트하고 dfs(1, pos[index], door2)
    • path와 cnt를 업데이트하고 dfs(2, pos[index], door2)
      • path와 cnt를 업데이트하고 dfs(3, pos[index], door2)
        • path와 cnt를 업데이트하고
          • dfs(4, pos[index], door2)
          • if문에 걸려서 ans를 업데이트하고 return (왼쪽문으로만 진행)
      • index=3 일때 더한 path, cnt 초기화
      • path와 cnt를 업데이트하고
        • dfs(4, door1, pos[index])
        • if문에 걸려서 ans를 업데이트하고 return (마지막은 오른쪽문으로 진행)

• 위와 같이 진행하면서 모든 노드를 탐색하는 방법입니다.

• 지금은 일부만 살펴보았지만 계속 진행한다면 조건에 맞는 모든 경우를 탐색합니다.

Outro

• 뭔가 포스팅이 밍숭맹숭한 기분이 들지만 이론적인 설명은 좋은 포스팅이 많으니 생략해버렸습니다!