🐨BOJ#3293]MONKEY

from collections import deque

def read_ints():
    return map(int, input().split())

def main():
    N, S = read_ints()
    connections = []
    initial_state = []
    
    # 방과 연결 정보, 초기 잠금 상태를 입력받음
    for _ in range(N):
        data = list(read_ints())
        initial_state.append(data[0])
        connections.append(data[2:])
    
    # 스위치 정보 입력 받음
    switches = []
    for _ in range(S):
        data = list(read_ints())
        switches.append(data[1:])
    
    # 시작 방 번호와 바나나가 있는 방 번호 입력 받음
    A, B = read_ints()
    
    # 0-based index로 조정
    A -= 1
    B -= 1
    
    # BFS를 위한 준비
    queue = deque([(A, 0, tuple(initial_state))])
    visited = set((A, tuple(initial_state)))
    
    # BFS 실행
    while queue:
        current, steps, state = queue.popleft()
        
        # 바나나가 있는 방에 도착했는지 확인
        if current == B:
            print(steps)
            return
        
        # 현재 방에서 이동 가능한 다음 방 탐색
        for next_room in connections[current]:
            next_room -= 1  # 0-based index 조정
            if state[next_room] == 0 and (next_room, state) not in visited:
                visited.add((next_room, state))
                queue.append((next_room, steps + 1, state))
        
        # 스위치가 있는 방인 경우, 스위치를 눌러 상태를 변경
        if current < S:  # 스위치 방 범위 내
            new_state = list(state)
            for room in switches[current]:
                room -= 1  # 0-based index 조정
                new_state[room] = 1 - new_state[room]  # 상태 토글
            new_state = tuple(new_state)
            if (current, new_state) not in visited:
                visited.add((current, new_state))
                queue.append((current, steps, new_state))

if __name__ == "__main__":
    main()

 

원숭이가 미로 속에서 바나나를 찾아 최소한의 복도를 통과하도록 돕는 코드.

BFS(Breadth-First Search) 알고리즘을 사용하여 해결.

코드 설명

1. 필요한 모듈 및 함수 정의
   • collections 모듈에서 deque를 가져와서 BFS에 사용할 큐를 생성한다.
   • read_ints 함수는 입력된 정수를 읽어 리스트 형태로 반환한다.

   • from collections import deque
     
     def read_ints():
         return map(int, input().split())

2. 메인 함수 정의
   • main 함수는 프로그램의 주요 로직을 포함한다.
   • N은 방의 수, S는 스위치의 수이다.
   • connections 리스트는 각 방과 연결된 다른 방의 정보를 저장한다.
   • initial_state 리스트는 각 방의 초기 잠금 상태를 저장한다.

   • def main():
         N, S = read_ints()
         connections = []
         initial_state = []

3. 방과 스위치 정보 입력
   • 각 방의 초기 상태와 연결된 방들을 입력받아 저장한다.
   • 스위치 정보를 입력받아 switches 리스트에 저장한다.

   • for _ in range(N):
         data = list(read_ints())
         initial_state.append(data[0])
         connections.append(data[2:])
     
     switches = []
     for _ in range(S):
         data = list(read_ints())
         switches.append(data[1:])

4. 시작 방과 바나나가 있는 방 정보 입력
   • 시작 방 A와 바나나가 있는 방 B를 입력받고, 0-based index로 조정한다.

   • A, B = read_ints()
     A -= 1
     B -= 1

5. BFS 준비
   • BFS를 위해 큐를 초기화하고, 시작 방의 상태를 큐에 넣는다.
   • 방문한 상태를 기록하기 위해 visited 집합을 초기화한다.

   • queue = deque([(A, 0, tuple(initial_state))])
     visited = set((A, tuple(initial_state)))

6. BFS 실행
   • 큐가 빌 때까지 반복하면서 BFS를 수행한다.
   • 현재 방이 바나나가 있는 방인지 확인하고, 맞다면 steps를 출력하고 종료한다.
   • 현재 방에서 이동 가능한 다음 방들을 탐색하고, 방문하지 않은 방이면 큐에 추가한다.
   • 스위치가 있는 방인 경우, 스위치를 눌러 방의 상태를 변경하고 새로운 상태로 큐에 추가한다.

while queue:
    current, steps, state = queue.popleft()
    
    if current == B:
        print(steps)
        return
    
    for next_room in connections[current]:
        next_room -= 1
        if state[next_room] == 0 and (next_room, state) not in visited:
            visited.add((next_room, state))
            queue.append((next_room, steps + 1, state))
    
    if current < S:
        new_state = list(state)
        for room in switches[current]:
            room -= 1
            new_state[room] = 1 - new_state[room]
        new_state = tuple(new_state)
        if (current, new_state) not in visited:
            visited.add((current, new_state))
            queue.append((current, steps, new_state))

예시 데이터의 커리과정

예시 입력 1:

4 1
0 1 3
1 2 3 4
0 2 1 2
0 1 2
1 2
3 4

• N = 4, S = 1
• 각 방의 초기 상태와 연결된 방:

  Room 1: Unlocked, connects to 3
  Room 2: Locked, connects to 3, 4
  Room 3: Unlocked, connects to 1, 2
  Room 4: Unlocked, connects to 2
  

• 스위치:

  Switch in Room 1 toggles Room 2
  

• 시작 방: 3, 바나나가 있는 방: 4

BFS 진행:

1. 시작 방 3: 현재 상태 (0, 1, 0, 0), 연결된 방 1, 2 방문.
2. 방 1로 이동: 상태 변화 없음, 연결된 방 3 방문.
3. 방 2로 이동: 상태 변화 없음, 연결된 방 3, 4 방문. 바나나 방 도착.
4. 결과: 최소 4번의 복도를 지나 바나나 방 도착.

이와 같은 방식으로 문제를 해결한다.