[백준 5547] 일루미네이션

🍎[백준 5547] 일루미네이션

문제링크

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

5547번: 일루미네이션

 

⚾ 코드

import sys
from collections import deque
input = sys.stdin.readline

m, n = map(int, input().split())
temp = [list(map(int, input().split())) for _ in range(n)]

# 입력 받은 리스트의 위, 아래, 좌, 우에 테두리를 씌워줄 역할을 할 큰 리스트를 만듦.
grid = [[0]*(m+2) for _ in range(n+2)]
for i in range(1, n+1):
    for j in range(1, m+1):
        grid[i][j] = temp[i-1][j-1]
visited = [[False]*(m+2) for _ in range(n+2)]

# 짝수행 -> 오른쪽 위, 오른쪽 아래, 윈쪽 위, 왼쪽 아래, 왼쪽, 오른쪽
dx_even = [-1, 1, -1, 1, 0, 0]
dy_even = [0, 0, -1, -1, -1, 1]

# 홀수행 -> 왼쪽 위, 왼쪽 아래, 오른쪽 위, 오른쪽 아래, 왼쪽, 오른쪽
dx_odd = [-1, 1, -1, 1, 0, 0]
dy_odd = [0, 0, 1, 1, -1, 1]


def check_range(x, y):
    if x >= 0 and y >= 0 and x < n+2 and y < m+2:
        return True
    return False


def bfs(x, y):
    q = deque([(x, y)])
    visited[x][y] = True
    cnt = 0
    while q:
        x, y = q.popleft()
        for i in range(6):  # 6방향 탐색
            if x % 2 == 0:
                nx = x+dx_even[i]
                ny = y+dy_even[i]
            else:
                nx = x+dx_odd[i]
                ny = y+dy_odd[i]

            if check_range(nx, ny):
                if grid[nx][ny] == 1:  # 만약 벽과 만난다면
                    cnt += 1  # 카운트 증가
                elif grid[nx][ny] == 0 and not visited[nx][ny]:  # 벽이 아니고 아직 방문하지 않았다면 deque에 삽입
                    visited[nx][ny] = True
                    q.append((nx, ny))
    return cnt


print(bfs(0, 0))

 

🔔 해결 과정 & 깨달은 점

- 관점을 달리 해서 풀었으면 더 빨리 풀 수 있었을 것 같은 문제였다.

- 푸는데 3일정도 걸렸다. 꽤 오랜 시간 풀었는데, 그 과정에서 깨달은 게 많아 그래도 의미있는 시간이었다.

- 관점을 달리하여 풀었으면 좋았을 것 같다고 느꼈던 이유는 나는 안쪽에서 바깥쪽을 계산하려 했다. 그러다 보니 생각해야할 예외상황들이 너무 많았다. 

 

6면이 둘러싸인 곳을 1로 채우면 될까? 라고 생각했지만, 그렇지 않은 경우가 있다는 사실또한 알았다.

 

관점을 바꾸어 바깥에서 접근해보았더니 문제가 바로 풀렸다.

안이 아니라 바깥에서 보니 굳이 안에 있는 벽들을 신경쓰지 않아도 되었던 것이다!

 

홀수와 짝수행을 나누어 dx, dy를 만든 것도 스스로 생각해낼 수 있어 뿌듯했다.

 

다음에 이러한 문제를 또 만나게 된다면, 관점을 달리해서 풀어보자!