99클럽 코테 스터디 18일차 TIL, 백준 / 일루미네이션 / 5547

🔑 오늘의 학습 키워드 : bfs

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

 

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

w,h = map(int,input().split())

jido = [[0]*(w+2)]
for _ in range (h):
    jido.append([0] + list(map(int,input().split())) +[0])
jido.append([0]*(w+2))

di = [
    [(-1,-1),(0,-1),(1,0),(0,1),(-1,1),(-1,0)],
    [(0,-1),(1,-1),(1,0),(1,1),(0,1),(-1,0)]
]

def in_range(x,y):
    return 0<=x<(w+2) and 0<=y<(h+2)

def bfs(i,j):
    queue = deque([(i,j)])
    visited = set()
    paint = 0
    while queue:
        y,x = queue.popleft()
        for dx,dy in di[y%2]:
            nx ,ny = x + dx , y + dy
            if in_range(nx,ny):
                if jido[ny][nx] == 1:
                    paint += 1
                elif jido[ny][nx] == 0 and (nx,ny) not in visited:
                    visited.add((nx,ny))
                    queue.append((ny,nx))      
    return paint

print(bfs(0,0))

 

🗒️ 공부한 내용 본인의 언어로 정리하기

🤔 문제를 보고 든 생각

6각형 모양을 어떻게 처리할 수 있을지를 고민해보고

 

외벽에만 닿는 부분을 어떻게 처리할 수 있어야할지를 고민해봐야 겠다고 생각했다.

⏰ 예상 시간 복잡도 O( w * h )

제한 사항

첫째 줄에 두 개의 정수 W와 H가 주어진다. (1 ≤ W, H ≤ 100) 다음 H줄에는 상근이네 집의 건물 배치가 주어진다. i+1줄에는 W개의 정수가 공백으로 구분되어 있다. j번째 (1 ≤ j ≤ w) 정수의 좌표는 (j, i)이며, 건물이 있을 때는 1이고, 없을 때는 0이다. 주어지는 입력에는 건물이 적어도 하나 있다.

지도는 다음과 같은 규칙에 의해 만들어졌다.

• 지도의 가장 왼쪽 위에 있는 정육각형의 좌표는 (1,1)이다.
• (x,y)의 오른족에 있는 정육각형의 좌표는 (x+1,y)이다.
• y가 홀수 일 때, 아래쪽에 있는 정육각형의 좌표는 (x,y+1)이다.
• y가 짝수 일 때, 오른쪽 아래에 있는 정육각형의 좌표는 (x,y+1)이다.

😎 알고리즘 개요

dx, dy 설정

다른 bfs와 비슷하지만 이번 문제는 지도를 어떻게 만들어졌는지에 의해 dx, dy를 설정을 해줘야 한다.

 

세로가 홀수인 경우와 짝수인 경우를 나눠서 dx, dy를 나눠주면 된다.

di = [
    [(-1,-1),(0,-1),(1,0),(0,1),(-1,1),(-1,0)],
    [(0,-1),(1,-1),(1,0),(1,1),(0,1),(-1,0)]
]

 

홀수인 경우 왼쪽 상단이 되려면 (0, -1)을 해줘야하는데 

짝수인 경우는 왼쪽 상단에 (-1,-1)을 해줘야 하는 것을 알 수 있다.

 

bfs

이 부분이 문제를 푸는 핵심 로직이다

 

지도를 가지고 보면 맞닿아 있는 부분을 어떻게 구분을 하며, 내부에 있는지 외부에 있는지 구분을 해야하는 것일까 하는 의문이 드는데

 

1인 부분을 주위로 6방향 돌려가며 0인 부분과 만나면 페인트를 칠하면 된다고 생각을 했다.

 

그렇게하니 가장 외부에 있는 부분을 처리하기 위해서 입력을 받을 때 0으로 둘러줬다.

graph = [[0] * (w + 2)]
for _ in range(h):
    graph.append([0] + list(map(int, input().split())) + [0])
graph.append([0] * (w + 2))

 

그리고 0,0부터 시작하여 0을 만나 확장해가는 bfs를 했고 1을 만나면 1번 칠하는 그러한 로직으로 풀이했다.

 

✅ 오늘의 회고

- 지도에 따라 방향을 설정하는 문제를 처음 본건 아니지만 6각형은 신선했던 것 같다.

 

#99클럽 #코딩테스트준비 #개발자취업 #항해99 #TIL