카테고리 없음

[백준/파이썬][Gold V] 와드 - 23747

난쟁이 개발자 2025. 1. 21. 14:09
반응형

[Gold V] 와드 - 23747

문제 링크

성능 요약

메모리: 174512 KB, 시간: 420 ms

분류

너비 우선 탐색, 그래프 이론, 그래프 탐색, 구현, 시뮬레이션

제출 일자

2025년 1월 21일 13:59:51

문제 설명

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

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

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

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

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

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

입력

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

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

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

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

출력

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

풀이

from collections import deque

R, C = map(int, input().split())
board = [list(input()) for _ in range(R)]

sr, sc = map(int, input().split())
sr, sc = sr - 1, sc - 1

cmd = list(input())

dr = [-1, 1, 0, 0]
dc = [0, 0, -1, 1]

for c in cmd :
    if c == 'W' :
        q = deque()
        area_seperator = board[sr][sc]
        if area_seperator == '.' :
            continue
        q.append((sr, sc))
        board[sr][sc] = '.'
        while q :
            cr, cc = q.popleft()
            for d in range(4) :
                nr, nc = cr + dr[d], cc + dc[d]
                if 0 <= nr < R and 0 <= nc < C and board[nr][nc] == area_seperator :
                    board[nr][nc] = '.'
                    q.append((nr, nc))

    elif c == 'U' :
        sr -= 1
    elif c == 'D' :
        sr += 1
    elif c == 'L' :
        sc -= 1
    elif c == 'R' :
        sc += 1

board[sr][sc] = '.'
for d in range(4) :
    nr, nc = sr + dr[d], sc + dc[d]
    if 0 <= nr < R and 0 <= nc < C :
        board[nr][nc] = '.'

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

        else :
            print('.', end='')
    print()

나중에 다시 풀어봐야겠다. 

아직은 그래프 + 구현 문제는 어렵다. 

주어지는 커맨드를 먼저 수행한 후 마지막 장소에서 상하좌우로 시야 확보 한다.

커맨드는 총 5가지로 상, 하, 좌, 우, 와드 가 있는데 상 하 좌 우는 보드를 그려보면 쉽게 이해할 수 있다.

와드는 연결된 문자를 모두 "." 으로 바꾼 후 다시 커맨드를 수행하면 된다. 

나머지 커맨드는 현재 위치를 계속해서 이동 시키고 도착한 장소에서 인접한 상 하 좌 우 시야 확보를 하면 되는 풀이이다.

이런 구현 문제는 막상 풀어보면 쉽게 이해되고 감이 잡히는 느낌이다. 

이런 문제는 많이 접해보고 손으로 써보고 하는게 답인 듯 하다. 머리속에만 생각하던대로 구현하는것이 아니라 머리속에 있는 걸 손으로 풀어 쓴 후 풀어 쓴 걸 보면서 구현하는 습관을 들여야 겠다. 

반응형