[코딩 인터뷰][HackerRank] Hexagonal Grid

※ 이 포스트는 HackerRank 문제인 Hexagonal Grid 해설을 담고 있습니다.
본 풀이는 Optimal하지 않을 수 있으며, HackerRank에서의 Submission 통과만을 보장합니다.

Hexagonal Grid

문제 출처 : https://www.hackerrank.com/challenges/hexagonal-grid/problem
카테고리 : BFS or DFS
난이도 : Hard (70 point)

문제 설명

두 줄의 육각형 Grid가 주어진다. 인접한 Grid들은 한 변씩을 공유하고 있는데, 자세한 건 아래 그림을 봐야할 것 같다.

<출처> – HackerRank

여기서 다음과 같은 1 x 2 크기의 Grid로 주어진 Grid를 모두 채울 수 있는지 여부를 출력해야한다.

맨 위의 두 줄의 Grid에서 두 줄은 항상 같은 길이를 가진다. 위 예제에선 N = 6인 경우다.
N이 주어진 후에, 각각의 줄이 입력으로 주어지는데, 위처럼 회색인 곳은 Grid를 놓을 수 있는 빈 곳으로 0으로 표시된다. 반대로 검은색인 곳은 Grid를 놓을 수 없는데, 이 곳은 1로 표시된다.

문제 풀이

문제를 해결하기 위한 두 가지 포인트가 존재한다.
첫째로, 검은색 Grid가 회색 Grid 영역을 서로 단절시킬 수 있다면, 두 영역은 별도로 계산해도 괜찮다는 점이다. 아래와 같은 입력을 생각해보자.

7
0100000
0100000
N = 3이고 두 줄에 대한 Grid 상태가 다음과 같이 주어졌다. 이런 경우에 검은색 Grid에 의해서 왼쪽의 회색 Grid들과, 오른쪽의 회색 Grid들은 완전히 분리되어있다.

둘째로는 연결된 회색 Grid영역은 모양에 상관없이, 총 Grid의 수가 짝수이기만 하면 1 x 2 Grid로 무조건 채울 수 있다는 점이다. 직관적으로 찾아낼 수도 있고, 증명할 수도 있다. 다른 Grid와 공유하는 변의 수가 가장 적은 Grid부터 차례로 채워나가면, 반드시 전체 영역을 채울 수 있다. 문제에서는 “YES”, “NO”만 출력하므로, 훨씬 간단하게 풀 수 있다.

코드

#!/bin/python3

import os
import sys

#
# Complete the hexagonalGrid function below.
#
def fillGrid(grid, x, y):
    vec = [[(0, 1), (0, -1), (1, -1), (1, 0)], [(0, 1), (0, -1), (-1, 0), (-1, 1)]]
    q = [(x, y)]
    cnt = 0
    while len(q) > 0:
        (x, y) = q.pop(0)
        for v in vec[x]:
            new_x, new_y = x + v[0], y + v[1]
            if new_x >= 0 and new_y >= 0 and new_x < len(grid) and new_y < len(grid[0]):
                if grid[new_x][new_y] == '0':         
                    q.append((new_x, new_y))
                    grid[new_x][new_y] = '1'

        cnt += 1
    return cnt

def hexagonalGrid(a, b):
    #
    # Write your code here.
    #
    arr = []
    arr.append([c for c in a])
    arr.append([c for c in b])
    
    for i in range(len(arr)):
        for j in range(len(arr[0])):
            if arr[i][j] == '0':
                arr[i][j] = '1'
                if fillGrid(arr, i, j) % 2 == 1:
                    return "NO"
    return "YES"

if __name__ == '__main__':
    fptr = open(os.environ['OUTPUT_PATH'], 'w')

    t = int(input())

    for t_itr in range(t):
        n = int(input())

        a = input()

        b = input()

        result = hexagonalGrid(a, b)

        fptr.write(result + '\n')

    fptr.close()

코딩 인터뷰 – Hexagonal Grid