(Python/파이썬) - 백준(BOJ) 23747번 : 와드

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

23747번: 와드

---

• 문제 : 

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

 

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

 

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

 

 

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

 

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

 

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

 

 

 

---

• 풀이 :

그래프 탐색의 개념이 추가된 구현 문제였습니다.

 

알고리즘의 흐름입니다.

 

1. 주어진 명령이 "W" 인 경우와 그 나머지의 경우로 나누어 줍니다.

 

2. "W"일 경우 이미 와드를 설치한 칸이 아니라면 BFS로 와드로 밝힐 영역을 탐색합니다.

 

3. 아닐 경우 dictionary에 저장된 dx,dy값을 R,C에 각각 더해주어 좌표를 이동시킵니다.

 

4. 모든 명령이 종료된 후 한별이의 위치와 사방의 시야를 밝혀줍니다.

 

 

 

---

• 소스코드 : 

import sys
from collections import deque
input = sys.stdin.readline

dxdy = {
    "L" : [0,-1],
    "R" : [0, 1],
    "U" : [-1, 0],
    "D" : [1, 0]
}

def ward(R,C, check): # 와드 설치
    queue = deque()
    queue.append([R,C])
    board[R][C] = "X"
    answer[R][C] = "."
    while queue:
        x,y = queue.popleft()
        for key in dxdy:
            ax = x + dxdy[key][0]
            ay = y + dxdy[key][1]
            if 0 <= ax < N and 0 <= ay < M and board[ax][ay] == check:
                board[ax][ay] = "X"
                answer[ax][ay] = "."
                queue.append([ax,ay])

N, M = map(int,input().split())
board = [list(input().strip()) for _ in range(N)]
answer = [["#" for _ in range(M)] for _ in range(N)]
R, C = map(int,input().split())
R, C = R-1, C-1
command = input().strip()

for c in command:
    if c == "W":
        if board[R][C] != "X": #이미 와드를 설치한 칸이 아닌 경우에만 와드 설치
            ward(R,C,board[R][C])
    else: # L,R,U,D의 경우
        R += dxdy[c][0]
        C += dxdy[c][1]


# 모든 명령이 종료된 후 현재 한별이의 위치와 사방의 시야는 확보되어야 함
answer[R][C] = "."
for key in dxdy:
    if 0 <= R+dxdy[key][0] < N and 0 <=  C+dxdy[key][1] < M:
        answer[R+dxdy[key][0]][C+dxdy[key][1]] = "."

#정답 출력
for i in answer:
    print(''.join(i))