[Gold V] 와드 - 23747

문제 링크

성능 요약

메모리: 49920 KB, 시간: 920 ms

분류

구현, 그래프 이론, 그래프 탐색, 시뮬레이션, 너비 우선 탐색, 격자 그래프, 플러드 필

문제 설명

한별이는 출근하던 도중 이세계 대환장 버스에 치였다.

그림 B.1: 이세계 대환장 버스

그림 B.2: 출근하는 한별이

올해 휴가를 전부 써 버려 당장 판교로 돌아가야 하는 한별이는 돌아가기 위한 방법을 어떻게든 찾아보기 위해 이세계를 돌아다녀 보려고 한다.

이세계는 $R\times C$의 격자로 되어 있다. 지금은 밤이어서 한별이는 자신이 위치한 칸 및 그 칸에서 위, 아래, 왼쪽 또는 오른쪽으로 인접한 칸만을 볼 수 있지만, 와드를 설치하면 조금 더 넓은 영역의 시야를 확보할 수 있다. 구체적으로는, 격자의 모든 칸은 각각 어떤 영역 하나에 속해 있는데, 와드를 놓으면 와드가 놓인 칸이 속한 영역에 있는 모든 칸을 볼 수 있게 된다.

한별이의 여행 기록이 주어질 때 한별이가 얼마나 넓은 시야를 확보했을지 계산해 보자.

입력

첫 번째 줄에는 격자의 크기를 나타내는 두 정수 $R$과 $C$가 주어진다. ($1 \le R,C \le 1,000$)

다음 줄부터 $R$개의 줄에 걸쳐 격자의 정보가 주어진다. 각 줄은 $C$개의 알파벳 소문자로 이루어져 있으며, 위, 아래, 왼쪽 또는 오른쪽으로 인접해 있는 칸이 같은 문자라는 것은 두 칸이 같은 영역에 속해 있음을 의미한다.

다음 줄에는 한별이가 이세계에 떨어진 위치를 나타내는 두 정수 $H_R$, $H_C$가 주어진다. 이는 한별이가 위에서 $H_R$번째 줄, 왼쪽에서 $H_C$번째 칸에 떨어졌음을 의미한다. ($1 \le H_R \le R$, $1 \le H_C \le C$)

마지막 줄에는 한별이의 여행 기록을 나타내는 $200,000$글자 이하의 문자열이 주어진다. 여행 기록의 각 문자는 U, D, L, R, W 중 하나로 이루어져 있으며, U, D, L, R은 각각 위, 아래, 왼쪽, 오른쪽으로 한 칸 이동했다는 뜻이고, W는 지금 있는 칸에 와드를 설치했다는 뜻이다. 한별이가 격자를 벗어나는 경우는 주어지지 않는다.

출력

$R$개의 줄에 걸쳐 한별이의 시야를 출력한다. 각 줄은 $C$개의 문자로 되어 있어야 하며, $R$번째 줄 $C$번째 문자가 .이라면 한별이의 시야에 해당 칸이 들어와 있다는 뜻이고 #이라면 그렇지 않다는 뜻이다.

---

문제 풀이

문제 분석

이 문제는 R x C 크기의 격자 형태의 이세계를 배경으로 합니다. 한별이는 이세계에서 주어진 이동(U, D, L, R)과 와드 설치(W) 명령을 수행합니다. 우리의 목표는 모든 명령을 수행한 후 한별이가 볼 수 있는 영역을 . (보임)과 # (안 보임)으로 표시하여 출력하는 것입니다.

입력:

• R, C: 격자의 행과 열 크기.
• graph: R개의 줄에 걸쳐 주어지는 C개의 소문자 문자열. 같은 문자를 가진 인접한 칸들은 같은 '영역'에 속합니다.
• H_R, H_C: 한별이가 처음 떨어진 1-based 인덱스 위치.
• arr: 한별이의 여행 기록을 담은 문자열. 각 문자는 이동(U, D, L, R) 또는 와드 설치(W)를 나타냅니다.

출력:

• R x C 크기의 시야 격자. 볼 수 있는 칸은 .으로, 볼 수 없는 칸은 #으로 표시됩니다.

시야 확보 규칙:

1. 와드 설치(W): 현재 한별이가 위치한 칸에 와드를 설치하면, 해당 칸이 속한 '영역'의 모든 칸이 보이게 됩니다. 여기서 '영역'이란 현재 칸과 같은 문자를 가지면서 상하좌우로 연결된 모든 칸들의 집합입니다.
2. 최종 위치에서의 시야: 모든 명령을 수행한 후, 한별이가 최종적으로 위치한 칸과 그 칸의 상하좌우 인접한 4칸은 항상 보이게 됩니다.

접근 방법

이 문제는 그래프 탐색의 일종인 **너비 우선 탐색 (BFS)**을 활용하여 해결할 수 있습니다.

1. 격자 그래프: 이세계는 R x C 격자 형태로 주어지므로, 각 칸을 노드로 보고 상하좌우 인접한 칸을 간선으로 연결된 그래프로 생각할 수 있습니다.
2. 와드 설치(W) 처리: 와드를 설치하면 현재 칸과 같은 문자를 가지는 연결된 모든 칸을 찾아야 합니다. 이는 격자에서 특정 시작점에서부터 연결된 구성 요소(connected component)를 찾는 전형적인 문제이며, BFS가 가장 효율적인 방법 중 하나입니다. BFS는 큐를 사용하여 시작점에서 가까운 노드부터 탐색하며, 방문한 노드를 표시하여 중복 탐색을 방지합니다.
3. 시야 상태 관리: 어떤 칸이 보이는지 여부를 저장할 별도의 R x C 크기의 2차원 배열(result)을 생성합니다. 초기에는 모든 칸이 # (안 보임) 상태이고, 와드 설치나 최종 위치 시야 확보 규칙에 따라 . (보임)으로 업데이트합니다.
4. 최종 시야 처리: 모든 명령을 처리한 후, 한별이의 최종 위치와 그 주변 4칸을 보이는 상태('.')로 만듭니다. 이는 와드 설치와는 별개의 규칙입니다.

구현 설명

주어진 코드는 다음과 같은 단계로 문제를 해결합니다.

1. 초기 설정 및 입력 처리

• sys.stdin.readline을 사용하여 입력 속도를 높입니다.
• directions = [(1,0),(-1,0),(0,1),(0,-1)]는 상하좌우 이동에 사용될 상대 좌표 변화량을 정의합니다.
• dir_map = {"L" : (0,-1), "R" : (0,1), "U" : (-1,0), "D" : (1,0)}는 여행 기록의 문자 명령을 실제 좌표 변화량에 매핑합니다.
• n, m = map(int, input().split())로 격자 크기를 읽습니다.
• graph는 이세계 지도의 문자를 저장하는 2차원 리스트입니다.
• x, y = map(int, input().split())로 한별이의 초기 위치를 읽고, 0-based 인덱스로 변환하기 위해 x-=1, y-=1를 수행합니다.
• arr = list(input().strip())로 여행 기록을 문자 리스트로 저장합니다.
• result = [["#"] * m for i in range(n)]는 한별이의 시야를 저장할 2차원 리스트를 생성하고, 모든 칸을 # (안 보임)으로 초기화합니다.

2. BFS 함수 정의 (BFS(i, j))

• 이 함수는 한별이가 와드를 설치한 위치 (i, j)에서 시작하여, 해당 위치와 같은 문자를 가지는 연결된 모든 칸을 찾아 . (보임)으로 표시합니다.
• queue = deque([(i,j)]): BFS를 위한 큐를 생성하고 시작 위치를 넣습니다.
• target = graph[i][j]: 현재 칸의 문자(영역을 구분하는 기준)를 저장합니다.
• result[i][j] = ".": 시작 칸은 무조건 보이게 만듭니다.
• while queue:: 큐가 빌 때까지 반복합니다.
  • x,y = queue.popleft(): 큐에서 현재 칸을 꺼냅니다.
  • for dx,dy in directions:: 현재 칸의 상하좌우 4방향 이웃을 확인합니다.
    • sx,sy = x+dx,y+dy: 이웃 칸의 좌표를 계산합니다.
    • if 0<=sx<n and 0<=sy<m: 이웃 칸이 격자 범위 내에 있는지 확인합니다.
    • and graph[sx][sy] == target: 이웃 칸이 현재 영역과 같은 문자인지 확인합니다.
    • and result[sx][sy] == "#": 이웃 칸이 아직 보이지 않는 상태(#)인지 확인합니다. 이 조건은 매우 중요합니다. 이미 보이는 칸은 중복해서 탐색할 필요가 없으므로 효율성을 높여줍니다.
    • 위의 모든 조건을 만족하면, queue.append((sx,sy))로 이웃 칸을 큐에 추가하고 result[sx][sy] = "."으로 보이는 상태로 업데이트합니다.

3. 여행 기록 처리 및 현재 위치 시야 확보

• for op in arr:: 여행 기록(arr)의 각 명령을 순서대로 처리합니다.
  • if op == "W":: 명령이 와드 설치라면
    • if result[x][y] == "#": BFS(x,y): 현재 한별이가 서 있는 칸 (x, y)가 아직 보이지 않는 상태라면 (즉, 해당 영역이 아직 탐색되지 않았다면) BFS 함수를 호출하여 해당 영역 전체를 보이게 합니다. 이 조건은 BFS를 불필요하게 여러 번 호출하는 것을 막아 성능을 최적화합니다.
  • else:: 명령이 이동(U, D, L, R)이라면
    • dx,dy = dir_map[op]: 해당 명령에 맞는 좌표 변화량을 가져옵니다.
    • x+=dx; y+=dy: 한별이의 현재 위치를 업데이트합니다.
• look_around(x,y) 함수는 코드에는 정의되어 있지 않지만, 주석으로 이 단계가 끝난 후 look_around 함수가 호출되는 것처럼 보입니다. 실제 코드는 for row in result: print("".join(row)) 전에 look_around(x,y)를 호출합니다.
  • 이 함수는 한별이의 최종 위치 (x,y)와 그 주변 상하좌우 칸들을 .으로 만듭니다. 이는 와드 설치와 관계없이 최종적으로 무조건 보이게 되는 칸들을 처리합니다.

4. 결과 출력

• for row in result:: 최종 시야를 담고 있는 result 2차원 리스트의 각 행에 대해 반복합니다.
• print("".join(row)): 각 행의 문자들을 공백 없이 합쳐서 출력합니다.

⏱복잡도 분석

• 시간 복잡도: O(R * C + L)

  • 입력 처리: graph를 읽는 데 O(R * C), 명령 문자열 arr를 읽는 데 O(L) (여기서 L은 arr의 길이)가 걸립니다.
  • result 초기화: O(R * C).
  • 명령 처리 루프: L번 반복됩니다.
    • 이동 명령: 각 이동은 O(1) 시간이 걸립니다.
    • 와드 설치 명령 (W): BFS 함수가 호출됩니다. 모든 BFS 호출을 통틀어, 격자 내의 각 칸은 한 번만 큐에 추가되고 처리됩니다 (왜냐하면 result[sx][sy] == "#" 조건으로 이미 방문한 칸은 다시 탐색하지 않기 때문입니다). 따라서 모든 BFS 호출의 총 시간 복잡도는 O(R * C)입니다.
  • 최종 look_around: O(1) (최대 5칸 확인).
  • 결과 출력: O(R * C).
  • 종합적으로 O(R * C + L)이 됩니다. R, C <= 1000이므로 R*C <= 10^6이고, L <= 2*10^5이므로, 전체 연산은 약 1.2 * 10^6 정도로 충분히 빠릅니다.

• 공간 복잡도: O(R * C)

  • graph (격자 정보): O(R * C) 공간을 사용합니다.
  • result (시야 정보): O(R * C) 공간을 사용합니다.
  • queue (BFS 내부): 최악의 경우 (모든 칸이 하나의 영역일 때) O(R * C) 칸이 큐에 들어갈 수 있습니다.
  • 종합적으로 O(R * C) 공간 복잡도를 가집니다. 1000 * 1000 칸은 대략 1MB 정도의 메모리를 사용하므로, 메모리 제약 (49920 KB = 약 48 MB) 내에 충분히 들어옵니다.

핵심 포인트

1. BFS를 이용한 영역 탐색: '와드 설치' 명령(W)은 현재 위치와 같은 문자를 가진 연결된 모든 칸(즉, 하나의 연결된 영역)을 찾아내야 합니다. 이는 격자에서 BFS를 적용하여 효율적으로 탐색할 수 있는 전형적인 플러드 필(Flood Fill) 문제에 해당합니다.
2. 중복 BFS 방지 최적화: if result[x][y] == "#": BFS(x,y) 조건은 매우 중요합니다. 이미 와드에 의해 시야가 확보된 영역은 다시 BFS를 수행할 필요가 없습니다. 이 조건을 통해 전체 BFS 연산의 총 복잡도가 O(R*C)로 유지되어 시간 초과를 방지합니다.
3. 최종 위치 시야 규칙: 와드 설치와 별개로, 모든 명령 처리 후 한별이의 최종 위치와 그 인접 4칸은 항상 보이게 됩니다. 이 규칙은 look_around 함수를 통해 모든 명령 처리 for 루프 이후에 한 번만 적용됩니다.

풀이 코드

import sys
from collections import deque

def BFS(i,j):
    queue = deque([(i,j)])

    target = graph[i][j]

    result[i][j] = "."

    while queue:
        x,y = queue.popleft()
        for dx,dy in directions:
            sx,sy = x+dx,y+dy
            if 0<=sx<n and 0<=sy<m and graph[sx][sy] == target and result[sx][sy] == "#":
                queue.append((sx,sy))
                result[sx][sy] = "."

def look_around(x,y):
    result[x][y] = "."
    for dx,dy in directions:
        sx,sy = x+dx,y+dy
        if 0<=sx<n and 0<=sy<m:
            result[sx][sy] = "."

input = sys.stdin.readline

directions = [(1,0),(-1,0),(0,1),(0,-1)]
dir_map = {"L" : (0,-1), "R" : (0,1), "U" : (-1,0), "D" : (1,0)}

n,m = map(int, input().split())

graph = []
for i in range(n):
    graph.append(list(input().strip()))

x,y = map(int, input().split())
x-=1
y-=1

arr = list(input().strip())

result = [["#"] * m for i in range(n)]

for op in arr:
    if op == "W":
        if result[x][y] == "#":
            BFS(x,y)
    else:
        dx,dy = dir_map[op]
        x+=dx 
        y+=dy

look_around(x,y)

for row in result:
    print("".join(row))