백준 - 23747번 와드

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

23747번: 와드

나는 보통 이 문제처럼 좌표를 이용한 문제는 DFS/BFS 문제라고 생각하고 접근한다.

실제로 이 문제는 DFS/BFS 를 이용해서 풀 수 있다.

 

그럼 이 알고리즘을 어디서 사용해야 할까를 고민해보자.

문제를 읽어보면 여정에 따라 좌표를 옮겨가며 맵을 이동하다가 W 문자가 있다면 현좌표와 같은 값을 가진 좌표들에 모두 불을 밝힌다.

그렇다.

와드를 박을때 DFS/BFS 를 사용하면 된다.

이것만 알면 이제 머릿속에 있는 생각의 흐름을 코드로 옮기기만 하면 된다.

 

나는 우선 DFS 고 BFS 고 자시고, 현 위치에서 여행 기록에 따라 옮겨다녀야 하기 때문에 이 부분부터 코드로 옮겼다.

현 좌표값에서 상하좌우로 옮겨갈 수 있게 셋팅을 해주었다. 

그리고 여행 기록 리스트에서 반복문을 돌면서 어느 위치로 이동해야하는지, 혹은 와드를 박아야하진 않는지 판별해준다.

또 중요한 포인트는, 여행이 끝나고 마지막에 내가 서있는 위치에서는 내 사방에 불을 밝혀주어야 하기 때문에 이 부분도 한번 더 판별해준다.

 

이제 중요한 와드를 박을때이다. 나는 처음엔 DFS 로 코드를 짰다. 그런데 그러면 테스트케이스는 통과하지만, 시간초과가 나게 된다.

오래 고민해 봤지만, 파이썬으로 풀때는 DFS로는 이 문제를 통과할 수 없다고 결론을 내리게 되었다.

또한 나는 재귀를 이용해서 코드를 짰는데, 파이썬에서 재귀를 호출할 수 있는 스택의 한계가 있기 때문에 맵이 크면 이 방법으로는 답을 얻을 수 가 없다.

또한 BFS 가 DFS 보다 빠르기 때문에, 정말 DFS 로만 풀어야하는 상황이 아니라면 BFS 로 문제를 푸는것이 나을것 같다.

 

아무튼 그래서 queue를 사용하는 BFS 로 코드를 수정했다.

아래는 최종 제출 코드이다.

from collections import deque

r, c = map(int, input().split(' '))

my_map = []

for _ in range(r):
    my_li = list(input())
    my_map.append(my_li)


cur_x, cur_y = map(int, input().split(' '))

cur_position = [cur_x-1, cur_y-1]

travel_record = input()

directions = {'U': [-1, 0], 'D': [1, 0], 'R': [0, 1], 'L': [0, -1]}

global result
result = [['#' for _ in range(c)] for _ in range(r)]

def ward(cur_position, my_map, target_alph, result):
    dx, dy = [-1, 1, 0, 0], [0, 0, -1, 1]
    queue = deque()
    x, y = cur_position

    my_map[x][y] = 'visited'
    result[x][y] = '.'

    queue.append([x, y])

    while queue:
        x_1, y_1 = queue.popleft()

        for i in range(4):
            x_2 = x_1 + dx[i]
            y_2 = y_1 + dy[i]

            if 0 <= x_2 < r and 0 <= y_2 < c and my_map[x_2][y_2] == target_alph and result[x_2][y_2] == "#":
                queue.append([x_2, y_2])
                my_map[x_2][y_2] = 'visited'
                result[x_2][y_2] = '.'


for i in range(len(travel_record)):
    if travel_record[i] == 'W':
        target_alph = my_map[cur_position[0]][cur_position[1]]
        ward(cur_position, my_map, target_alph, result)
        if i == len(travel_record)-1:
            last_x, last_y = cur_position

            result[last_x][last_y] = '.'
            for k in directions.keys():
                position = [x+y for x,y in zip(cur_position, directions[k])]
                x, y = position
                if 0 <= x < r and 0 <= y < c:
                    result[x][y] = '.'

    else:
        direction = directions[travel_record[i]]
        cur_position = [x+y for x,y in zip(cur_position, direction)]

        if i == len(travel_record)-1:
            last_x, last_y = cur_position

            result[last_x][last_y] = '.'
            for k in directions.keys():
                position = [x+y for x,y in zip(cur_position, directions[k])]
                x, y = position
                if 0 <= x < r and 0 <= y < c:
                    result[x][y] = '.'

for i in range(r):
    value = ('').join(result[i])
    print(value)