[백준 12946번] 육각보드(파이썬)

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

12946번: 육각 보드

이 문제는 어떻게 색을 칠할지 먼저 고려해야합니다.

https://astrid-dm.tistory.com/380

백준 12946번 육각 보드 (C++)

여기 참고자료가 있는데요.

최대로 칠할 수 있는 색은 3개입니다.

직접 그려보시면 이해가 더 편하실 겁니다.

(저같은 경우에는 저게 진짜 되는지 확인하려고

노트에 육각형 그리면서 테스트해봤습니다.)

 

이후에 진행은 이렇습니다.

1. 아직 방문 안한 곳--> 다른 색을 씀

-->최대 색 2개

2. 근처에 현재 색과 같은 색이 있음

-->최대 색 3개

#백준 12946번 육각보드
import sys
sys.setrecursionlimit(10**8)
N=int(input())
room=[list(input()) for _ in range(N)]
visited=[[-1]*N for _ in range(N)]
answer=0
dir=((-1,0),(-1,1),(0,1),(1,0),(1,-1),(0,-1))
def dfs(x,y,c):
    global answer
    answer=max(1,answer)
    visited[x][y]=c
    for d in range(6):
        nx=x+dir[d][0]
        ny=y+dir[d][1]

        if nx<0 or nx>=N or ny<0 or ny>=N:
            continue
        if room[nx][ny]=='X':
            if visited[nx][ny]==-1:
                answer=max(2,answer)
                dfs(nx,ny,(c+1)%2)
            elif visited[nx][ny]==c:
                print(3)
                exit(0)


for x in range(N):
    for y in range(N):
        if room[x][y]=='X' and visited[x][y]==-1:
            dfs(x,y,0)
print(answer)

참고로 이 문제같은 경우에는

pypy3로 제출하면

메모리초과가 발생합니다.

python3로 제출해야 무사하게 통과가 되므로

참고해주세요.

 

육각형이라는 그래프에 대한 이해가 필요한 문제.

일반적인 그래프가 아니라서 어려웠지만

다양한 그래프를 경험하기 좋은 문제입니다.

한번 고민해보시면서 문제를 푸시는 것도 좋아보입니다.