백준 - 로봇 청소기 (삼성 기출) / Gold 5 / 14503번

문제 📋

백준 삼성기출 - 로봇 청소기

풀이 📝

import sys

direction = {
    0: "NORTH",
    1: "EAST",
    2: "SOUTH",
    3: "WEST"
}

N, M = map(int, sys.stdin.readline().split())
row, col, way = map(int, sys.stdin.readline().split())
table = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]

cleaned = [[False]*M for _ in range(N)]  # 청소한지 체크.
stack = [(row, col)]  # dfs를 위한 stack
cnt = 0

while True:
    if stack:  # 새롭게 청소할 곳이 있으면 청소.
        row, col = stack.pop()
        cleaned[row][col] = True
        cnt += 1

    for _ in range(4):
        way = (way + 3) % 4  # 왼쪽으로 방향 전환

        if direction[way] == "NORTH":  # 전진 준비
            new_row = row - 1
            new_col = col
        elif direction[way] == "EAST":
            new_row = row
            new_col = col + 1
        elif direction[way] == "SOUTH":
            new_row = row + 1
            new_col = col
        elif direction[way] == "WEST":
            new_row = row
            new_col = col - 1

        if table[new_row][new_col] != 1 and not cleaned[new_row][new_col]:  # 나아갈 곳이 벽이 아니고 청소 안한 곳이면
            stack.append((new_row, new_col))  # 청소할 곳으로 추가
            break

    if not stack:  # 네방향 다 탐색했는데도 청소할 곳이 없으면
        if direction[way] == "NORTH":  # 후진 준비
            new_row = row + 1
            new_col = col
        elif direction[way] == "EAST":
            new_row = row
            new_col = col - 1
        elif direction[way] == "SOUTH":
            new_row = row - 1
            new_col = col
        elif direction[way] == "WEST":
            new_row = row
            new_col = col + 1

        if table[new_row][new_col] == 1:  # 뒤에 벽이라면 종료
            break
        else:  # 후진
            row = new_row
            col = new_col
print(cnt)

재밌게 푼 문제이다.
먼저 생각한것은 현재 지점을 청소하고 조건에 해당되는 다음 지점으로 이동 후
똑같은 행동을 반복하기 때문에 청소 할곳을 탐색하는 DFS 문제라고 판단했고
DFS 탐색을 진행하면서 청소한 횟수를 counting 해주면 된다고 생각했다.

보통 DFS문제를 재귀로 풀었던 탓에 이번엔 stack를 이용하기로 했다.
그런데 어차피 탐색 대상 노드를 하나씩 넣고 바로 꺼내기 때문에 사실 어떤 자료구조를 사용하든지 크게 상관은 없다.

cleaned 배열을 통해서 방문한 곳(청소한 곳)을 체크해줬으며
조건에 따라서 언제 break를 할지 판단하는 것이 로직 짜는데 중요했던 것 같다.