[BOJ/백준] 11967 불켜기 파이썬

문제 링크 : https://www.acmicpc.net/problem/11967

11967번: 불켜기

 

BFS + 구현 문제이다. 알고리즘 자체는 어렵지 않으나 상태값을 잘못 지정하여 틀리고 있었다.

문제는 간단하다.

맵에 특정칸에는 다른 칸의 조명을 켤수 있는 스위치가 있고, 주인공은 상하좌우로 조명이 켜진 칸으로만 이동이 가능하다.

한 스위치로 여러개의 조명을 컨트롤 가능하고 한 조명이 여러 스위치에 의해 컨트롤이 가능하다.

이동하면서 스위치가 있는 칸에 오면 해당 스위치에 맞는 모든 조명을 켠다.

이때 주인공이 킬 수 있는 모든 조명의 개수는 몇개인지 구하는 문제이다.

 

사용하는 자료구조는 다음과 같다.

스위치의 위치를 표시한 switch_board 2차원 배열

방의 상태를 표시한 board 2차원 배열

  : 0 이동 가능한 칸(조명이 켜짐), -2 이동 불가능한 칸, -1 조명이 있는 칸(아직 조명이 켜지지 않음)

각 스위치가 컨트롤 가능한 조명의 위치를 저장한 switch 1차원 배열

 

 

우선 입력으로 들어온 스위치와 조명정보로 배열을 채웠다.

스위치 마다 번호를 지정하여 switch_board에 표시한다.

그리고 switch의 해당 번호에 조명의 위치값을 추가해준다.

마지막으로 board에 조명의 위치는 -1로 표시해준다.

 

이제 이 배열을 가지고 BFS 수행한다.

먼저 현재 칸이 조명이 아직 켜지지 않은 칸인지 체크한다.

만약 조명이 켜지지 않은 칸 즉 해당 칸의 board 값이 -1 이라면 다음으로 진행하지 않고 다시 큐에 넣어 대기한다.

왜나면 조명이 켜질때 까지 기다리기 위함이다.

근데 어떤 칸도 조명이 켜지지 않아 다음으로 진행하지 못한다면 BFS를 종료하고 나가면 된다.

왜냐면 모든 칸이 이동불가능한 칸에 있기 때문이다.

 

다음 현재 칸이 스위치가 있는 칸인지 체크한다.

그런 칸이라면 switch에서 해당 스위치의 번호 접근하여 조명을 켜준다. 이때 조명이 꺼진 칸만 체크하여 개수를 세준다.

 

그 다음 동서남북으로 칸을 체크한다.

방문하지 않은 칸이고 board의 값이 -2가 아닌 경우만 이동하고 큐에 넣어 준다.

 

BFS를 진행하는대는 큐의 길이만큼 우선 돈다. 이유는 현재 시점에서 이동이 가능한지 아닌지 체크하기 위함이다.

코드를 보면 이해가 갈 것이다.

 

마지막으로 한가지 주의할 점이라면 (1,1) 시작칸도 개수를 세줘야한다.

from sys import stdin
from collections import deque

input = stdin.readline
dx = [-1,1,0,0]
dy = [0,0,-1,1]

n,m = map(int, input().split())
switch_board = [[0]*(n+1) for _ in range(n+1)]
board = [[-2]*(n+1) for _ in range(n+1)]

switch = [[]]
for _ in range(m):
    a,b,x,y = map(int, input().split())
    if switch_board[a][b] == 0:
        switch_board[a][b] = len(switch)
        switch.append([(x,y)])
    elif switch_board[a][b] > 0:
        switch[switch_board[a][b]].append((x,y))
    board[x][y] = -1

def solv():
    global board
    q = deque([(1,1)])
    board[1][1] = 0

    visited = [[False]*(n+1) for _ in range(n+1)]
    visited[1][1] = True
    cnt = 1
    while q:
        q_len = len(q)
        flag = False
        for _ in range(q_len):
            x,y = q.pop()

            if board[x][y] == -1:
                q.appendleft((x,y))
                continue

            flag = True
            if switch_board[x][y] != 0:
                for a,b in switch[switch_board[x][y]]:
                    if board[a][b] == -1:
                        board[a][b] = 0
                        cnt += 1

            for d in range(4):
                nx = x + dx[d]
                ny = y + dy[d]

                if point_validator(nx,ny,visited):
                    visited[nx][ny] = True
                    q.appendleft((nx,ny))
        if not flag:
            break
    print(cnt)

def point_validator(x,y,visited):
    if x <= 0 or y <= 0 or x > n or y > n:
        return False
    elif visited[x][y]:
        return False
    elif board[x][y] == -2:
        return False
    return True

solv()