[Python] 23747번 와드

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

23747번: 와드

---

 

22/11/21

 

 

BFS문제에 시뮬레이션을 곁들인 문제로, 문제에서 주어지는 상황을 그대로 시뮬레이션하여 쉽게 해결할 수 있는 문제이다.

 

다만, 파이썬으로 해결하려고 한다면 시간초과에 유의해서 접근해야 풀 수 있는 문제이다.

---

 

문제 접근 방식:

 

 

먼저, 문제에서 주어진 정보대로 그래프의 크기, 그래프, 한별이의 현재 위치, 여행 기록을 모두 입력으로 받았다.

 

이후, 한별이의 여행기록을 for문으로 하나하나 돌리며 시뮬레이션을 해보는데, 와드를 놓았다는 기록인 $W$를 제외한 나머지 기록들 $U, D, L, R$에서는 한별이의 현재 위치($H_r, H_c$)를 변경해주었다.

 

와드를 놓을 때에는 BFS를 진행해주는데, 현재 위치한 곳의 색깔을 $area \ seperator$에 저장해주고, BFS를 진행할 때 $area \ seperator$와 같은 색깔만 방문처리를 해줌으로써 BFS를 진행했다.

 

이때, 방문처리는 그래프를 직접 변경함으로써 해주었다.

 

 

여기서 한가지 중요한 점은, 그냥 이걸 진행하면 시간 초과가 난다는 점인데, BFS의 시간을 최대한 줄이기 위해 이미 방문처리가 되었던 곳은 BFS를 진행하지 않고 스킵함으로써 시간을 단축해야 한다.

 

맨 마지막에, 현재 내가 있는 위치를 기준으로 내 위치와 내 주변의 4방향에 있는 곳을 그래프 상에서 방문처리해주었다.

 

이후 출력할 때, 방문처리가 되지 않았던 곳(알파벳 상태로 그대로 남아있던 곳)은 '#'으로, 방문처리가 된 곳은 '.'을 출력함으로써 구현해주었다.

---

아래는 내가 위의 접근 방식과 같이 작성한 파이썬 코드이다. 더보기를 누르면 확인할 수 있다.

# 23747번 와드
# 구현, 시뮬레이션, 그래프 이론, 그래프 탐색, BFS
import sys
from collections import deque
input = sys.stdin.readline

R, C = map(int, input().rstrip().split())  # 격자의 크기를 나타내는 두 정수
graph = [list(input().rstrip()) for _ in range(R)]  # 격자의 정보
Hr, Hc = map(lambda x: int(x)-1, input().rstrip().split())  # 한별이의 위치
hanbyeol_travel_record = input().rstrip()  # 한별이의 여행 기록
dr = [-1, 1, 0, 0]
dc = [0, 0, -1, 1]

for command in hanbyeol_travel_record:
    if command == 'W':
        queue = deque()
        area_seperator = graph[Hr][Hc]
        if area_seperator == '.':
            continue
        queue.append((Hr, Hc))
        graph[Hr][Hc] = '.'
        while queue:
            row, col = queue.popleft()
            for i in range(4):
                now_r, now_c = row+dr[i], col+dc[i]
                if now_r < 0 or now_r >= R or now_c < 0 or now_c >= C:
                    continue
                if graph[now_r][now_c] == area_seperator:
                    graph[now_r][now_c] = '.'
                    queue.append((now_r, now_c))
    elif command == 'U':
        Hr -= 1
    elif command == 'D':
        Hr += 1
    elif command == 'L':
        Hc -= 1
    elif command == 'R':
        Hc += 1

graph[Hr][Hc] = '.'
for i in range(4):
    now_Hr, now_Hc = Hr+dr[i], Hc+dc[i]
    if 0 <= now_Hr < R and 0 <= now_Hc < C:
        graph[now_Hr][now_Hc] = '.'

for row in range(R):
    for col in range(C):
        if graph[row][col] != '.':
            print('#', end = '')
        else:
            print('.', end = '')
    print()