boj 백준 파이썬 5547 일루미네이션

출처:https://www.ioi-jp.org/joi/2011/2012-yo-prob_and_sol/2012-yo-t5/review/2012-yo-t5-review.html

 

육각형 관련한 탐색 문제 나오면
열2개,행1개 추가해서 배열을 확장하는 사고를 해야한다.

0에서 1과 접촉되면 갯수를 하나 추가해주면 된다.

중요한 것은 바깥쪽 1만 추가해줘야하니까 (0,0)에서 시작하여 0만 bfs 탐색해줘야한다.

풀이법을 알면 쉽고 모르면 굉장히 어렵게 느껴지는 문제

행 번호가 홀수일 때,짝수 일 때 왼쪽 아래,오른쪽 아래,왼쪽 위, 오른쪽 위가

다르다는 것이 까다로운 문제

보통 다국어가 쓰여있는 외국어 문제는 굉장히 참신하다는 느낌을 받는다.

 

import sys
from collections import deque
 
 
##(열,행)==(x,y)
 
## 행 번호가 홀 수 일때 왼쪽(행,열-1),오른쪽(행,열+1), 왼쪽 아래(행+1,열),오른쪽아래(행+1,열+1), 왼쪽 위(행-1,열), 오른쪽 위(행-1,열+1)
## 행 번호가 짝수 일때 왼쪽 (행,열-1), 오른쪽 (행,열+1), 왼쪽 아래 (행+1,열-1), 오른쪽아래 (행+1,열) , 왼쪽 위 (행-1,열-1), 오른쪽 위(행-1,열)
if __name__=='__main__':
    #sys.stdin=open("input.txt", "rt")
 
    w,h=map(int,input().split()) ## w=열의 개수 h=행의 개수
 
    graph=[list(map(int,input().split()))  for _ in range(h)]
 
    graph=deque(graph)
 
    graph.appendleft([0]*(w))
    graph.append([0]*(w))
 
    graph=list(graph)
 
    for i in range(h+2):
        graph[i].insert(0,0)
        graph[i].append(0)
 
 
    #print(graph)
    ch=[[-1]*(w+2) for _ in range(h+2)]
    ## 행 번호가 홀수 일때 (왼쪽,오른쪽,왼쪽 아래,오른쪽 아래,왼쪽 위,오른쪽 위)
    odd_x=[0, 0, +1, +1, -1, -1]  
    odd_y=[-1, +1, 0, +1, 0, +1]
 
    ## 행 번호가 짝수 일때 (왼쪽,오른쪽,왼쪽 아래,오른쪽 아래,왼쪽 위,오른쪽 위)
    even_x=[0, 0, +1, +1, -1, -1] 
    even_y=[-1, +1, -1, 0, -1, 0]
 
 
    q=deque()
 
    q.append((0,0))
    ch[0][0]=1
   
    wall_cnt=0
 
    while q:
        x,y=q.popleft()
       
        
       
        if x%2==0: #짝수
            for k in range(6):
                nx=x+even_x[k]
                ny=y+even_y[k]
 
                if 0<=nx<h+2 and 0<=ny<w+2:
                       if graph[nx][ny]==0:
                           if ch[nx][ny]==-1: ## 만약 방문하지 않았따면
                            q.append((nx,ny))
                            ch[nx][ny]=1
                       else:
                           wall_cnt+=1
 
 
        else: #홀수
             for k in range(6):
                nx=x+odd_x[k]
                ny=y+odd_y[k]
 
                if 0<=nx<h+2 and 0<=ny<w+2:
                       if graph[nx][ny]==0:
                           if ch[nx][ny]==-1: ## 만약 방문하지 않았따면
                            q.append((nx,ny))
                            ch[nx][ny]=1
                       else:
                           wall_cnt+=1
          
 
    print(wall_cnt)