[백준] 14271 : 그리드 게임 (Python)

 

출처 : https://www.acmicpc.net/problem/14271

 

---

 

아이디어

해당 문제는 상하좌우 근접 칸을 탐색해야 하는 문제이므로, 그래프 탐색 유형이다. 먼저, 그리드의 칸이 변하는 규칙을 바탕으로, 요구사항이 어떤 의미를 가지는지 파악해보자.

요구사항 파악

그리드 칸이 변하는 규칙 시각화

'크기가 무한대이고, 단위 정사각형으로 나누어져 있는 그리드'

해당 사진을 통해 알 수 있듯이, 2 by 2 행렬이 4 by 4로 점점 확장되는 모습을 확인해볼 수 있다. 만약, 확장되는 형식으로 그래프를 탐색해야 한다면 완전 탐색이 될 수 밖에 없으므로 O(n**2) 시간 복잡도를 가지게 된다.

완전 탐색을 피하기 위해서는 '행렬의 크기가 진짜 무한대인가'를 따져봐야 한다. 커지는 규칙이 존재하는데 그것이 K이다. 얼마나 커지는지는 후술하도록 한다.

 

'칸 C와 변을 인접한 네 개의 칸 중에서 적어도 한 칸이 살아있으면, C는 1초 후에도 살아있다. 그 외의 경우에는 죽어있다.'

죽은 점을 나타내는 '.'을 기준으로, 상하좌우에 살아있는 점 'o'가 존재한다면, 죽은 점 -> 살아있는 점으로 바뀐다는 의미이다. 그 외의 경우는 다음과 같은 상황 밖에 없다.

. . .

. o .

. . .

이런 경우에는 살아있는 점 상하좌우가 모두 죽었기에 죽은 점으로 바뀌어야 하는가? 라는 질문이 가능하다. 만약 바꾸게 되면 예제 입력 2번 케이스의 답이 달라지기 때문에, 그냥 살아있는 점은 그대로 놔둔다로 해석 가능하다. (이 부분은 문제 설명이 부족한..)

 

'동시에 변한다'

동시에 변한다는 의미는 한 점이 변했을 때도 고려하는게 아니라, 초기 입력 상태 기준에서 모든 점을 체크한 후 한번에 변경한다는 의미이다.

---

 

이러한 요구사항들을 바탕으로, BFS 탐색 설계를 진행하면 된다. 그렇다면, 이 때의 고려 사항들을 생각해보자.

BFS 고려사항 1 : 전역 배열의 크기(live_idxs_visited 배열의 크기)

전역 배열의 최대 크기를 구하는 과정

k에 따라, 행과 열이 커지는 규칙이 존재하며, 이를 통해 최대 배열의 크기는 3050 by 3050임을 알 수 있다. 그러므로, 이 전역 배열은 BFS 탐색 시 이용되는 배열(방문여부)이 될 것이며, 행렬의 원소는 죽은 점이냐 살아있는 점이냐의 정보(다음 자식 노드 찾기)가 들어가게 된다.

이 때, 원소를 저장할 때 인덱스를 조심해야 한다. 예제 입력 케이스들은 모두  n by m 행렬 기준이므로, 전역 배열 3050 by 3050에 저장하기 위해서는 평행 이동이 필요하다.

평행 이동 공식 구하기

2 by 2에서 4 by 4 행렬로 평행 이동한다고 가정한 상태로 공식을 구하는 과정을 시각화하였다. 이를 정리하자면 다음과 같다.

• K=1 일때, (x, y) -> (x+1,y+1)

이를 통해, 우리는 전역 배열 3050 by 3050에서의 최종 평행 이동 공식을 다음과 같이 일반화할 수 있다.

• K의 최대 범위는 1500이다.
• 그러므로, K=1500 일때, (x,y) -> (x+1500, y+1500)

그렇다면, 전역 배열을 통해 Queue를 어떤 식으로 설정해야 할까?

 

BFS 고려사항 2

전역 배열의 원소는 다음 자식 노드 O점을 찾기 위한 (죽은 점 또는 살아있는 점)이 들어간다. 또한, 살아있는 점만을 큐에 삽입한다고 하면 죽은 점들만 탐색을 진행하게 되므로, 살아있는 점들에 대해서는 모두 방문 처리가 되었다고 볼 수 있다.

그렇다면, 그래프 상에서 어떤 점들이 같은 레벨을 가지는지 체크가 필요하다. 이 그래프의 깊이(레벨)이 더욱 깊어지게 되는 원인은 k이다. 즉, 다음과 같이 큐의 ADT를 세울 수 있다.

• Queue = [(row_idx, col_idx, time)]
• (살아있는 점의 행좌표, 살아있는 점의 열좌표, 해당 점의 그래프 깊이==시간 k)

이 고려사항들을 모두 조합하여, 프로그램을 설계 및 구현하면 문제를 해결할 수 있다. 탐색의 자세한 과정은 정답 코드를 통해 확인 가능하다.

 

정답 코드

# https://www.acmicpc.net/problem/14271
# 그리드 게임
# 그래프탐색, bfs

input=__import__('sys').stdin.readline
deque=__import__('collections').deque

def bfs():
    global answer
    
    while q:
        x,y,time=q.popleft()
        answer+=1 # 전역배열[x][y]은 살아있는 점이므로, 답 갱신
        # 만약, 시간이 k이상이라면,
        # 큐에 남은 것들은 k이상일때의 살아있는 점들만 있다.
        # 이 점들에 대한 정답 갱신만 진행.
        if time>=k:
            continue
        # 해당 살아있는 점의 자식 노드 탐색
        for dx,dy in [(0,-1),(0,1),(1,0),(-1,0)]:
            nx,ny=x+dx,y+dy
            if 0<=nx<3100 and 0<=ny<3100:
                # 해당 자식노드가 죽은 점이라면
                if live_idxs_visited[nx][ny]==0:
                    q.append((nx,ny,time+1)) # 해당 자식노드 큐에 추가
                    live_idxs_visited[nx][ny]=1 # 살아있는 점으로 변경.

n,m=map(int,input().split())
live_idxs_visited=[[0]*3100 for _ in range(3100)] # 전역 배열. (크기는 3050으로 해도 됨)
q=deque([]) # x,y,time (살아있는 점만을 삽입)
answer=0

for i in range(n):
    l=[*input()[:-1]]
    for j in range(m):
        if l[j]=='o':
            x,y=i+1500,j+1500 # 평행이동
            live_idxs_visited[x][y]=1 # 전역 배열 원소 정보 삽입
            q.append((x,y,0))

k=int(input())
bfs()
print(answer)