이번 문제는 BFS를 통해 해결하였다. 처음에는 모든 좌표를 돌며 grid를 각 그룹들의 번호로 바꿔주고, 딕셔너리를 이용하여 각 그룹의 좌표들을 정리하였다. 그리고 주어지는 commands를 순회하며 W가 들어오면 해당 그룹의 딕셔너리 리스트를 확인하여 결과 리스트에 해당 좌표들을 반영하였다. 그러나 이 방법은 50% 정도에서 시간초과가 발생하였다.

다른 방법을 생각해보았고, W가 들어올 때만 BFS를 통해 그룹을 찾아내고, 만약 그룹에 이미 와드가 있다면 넘어가도록 구현한다면 시간을 줄일 수 있을 것이라는 생각이 들었다. 그래서 이러한 방법으로 접근하였고 해결할 수 있었다.

Code

오답 코드 (시간초과)

from collections import deque, defaultdict
r, c = map(int, input().split())
grid = [list(str(input())) for _ in range(r)]
hy, hx = map(int, input().split())
hy, hx = hy-1, hx-1
dy, dx = [-1, 1, 0, 0], [0, 0, -1, 1]
mapping = {'U': 0, 'D': 1, 'L': 2, 'R': 3}
commands = list(str(input()))
answer = [['#' for _ in range(c)] for _ in range(r)]
groups = defaultdict(list)
visited = [[False for _ in range(c)] for _ in range(r)]
num = 1
def wd(y, x, num):
    q = deque()
    q.append((y, x))
    visited[y][x] = True
    groups[num].append((y, x))
    tmp = grid[y][x]
    grid[y][x] = num
    while q:
        y, x = q.popleft()
        for i in range(4):
            ny, nx = y+dy[i], x+dx[i]
            if 0 <= ny < r and 0 <= nx < c and grid[ny][nx] == tmp and not visited[ny][nx]:
                groups[num].append((ny, nx))
                grid[ny][nx] = num
                visited[ny][nx] = True
                q.append((ny, nx))
for i in range(r):
    for j in range(c):
        if not visited[i][j]:
            wd(i, j, num)
            num += 1
for command in commands:
    if command == 'W':
        for y, x in groups[grid[hy][hx]]:
            answer[y][x] = '.'
    else:
        d = mapping[command]
        hy, hx = hy+dy[d], hx+dx[d]
answer[hy][hx] = '.'
for i in range(4):
    ny, nx = hy+dy[i], hx+dx[i]
    if 0 <= ny < r and 0 <= nx < c:
        answer[ny][nx] = '.'
for i in range(r):
    print(''.join(answer[i]))

정답 코드

from collections import deque
r, c = map(int, input().split())
grid = [list(str(input())) for _ in range(r)]
hy, hx = map(int, input().split())
hy, hx = hy-1, hx-1
dy, dx = [-1, 1, 0, 0], [0, 0, -1, 1]
mapping = {'U': 0, 'D': 1, 'L': 2, 'R': 3}
commands = list(str(input()))
answer = [['#' for _ in range(c)] for _ in range(r)]
visited = [[False for _ in range(c)] for _ in range(r)]
num = 1
def wd(y, x, num):
    q = deque()
    q.append((y, x))
    visited[y][x] = True
    tmp = grid[y][x]
    grid[y][x] = num
    answer[y][x] = '.'
    while q:
        y, x = q.popleft()
        for i in range(4):
            ny, nx = y + dy[i], x + dx[i]
            if 0 <= ny < r and 0 <= nx < c and grid[ny][nx] == tmp and not visited[ny][nx]:
                grid[ny][nx] = num
                answer[ny][nx] = '.'
                visited[ny][nx] = True
                q.append((ny, nx))
for command in commands:
    if command == 'W':
        if str(grid[hy][hx]).isalpha():
            wd(hy, hx, num)
            num += 1
    else:
        d = mapping[command]
        hy, hx = hy+dy[d], hx+dx[d]
answer[hy][hx] = '.'
for i in range(4):
    ny, nx = hy+dy[i], hx+dx[i]
    if 0 <= ny < r and 0 <= nx < c:
        answer[ny][nx] = '.'
for i in range(r):
    print(''.join(answer[i]))