[구현] 백준 14503: 로봇 청소기

문제: 로봇 청소기와 방의 상태가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오.

로봇 청소기가 있는 방은 N * M 크기의 직사각형으로 나타낼 수 있으며, 1 * 1 크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 벽 또는 빈 칸이다. 청소기는 바라보는 방향이 있으며, 이 방향은 동, 서, 남, 북 중 하나이다. 방의 각 칸은 좌표 (r, c)로 나타낼 수 있고, 가장 북쪽 줄의 가장 서쪽 칸의 좌표가 (0, 0), 가장 남쪽 줄의 가장 동쪽 칸의 좌표가 (N - 1, M - 1)이다. 즉, 좌표 (r, c)는 북쪽에서 (r + 1)번쨰에 있는 줄의 서쪽에서 (c + 1)번째 칸을 가리킨다. 처음에 빈 칸은 청소되지 않은 상태이다.

 

로봇 청소기는 다음과 같이 작동한다.

 

1. 현재 칸이 아직 청소되지 않은 경우, 현재 칸을 청소한다.

2. 현재 칸의 주변 4칸 중 청소되지 않은 빈 칸이 없는 경우,

    1. 바라보는 방향을 유지한 채로 한 칸 후진할 수 있다면 한 칸 후진하고 1번으로 돌아간다.

    2. 바라보는 방향의 뒤쪽 칸이 벽이라 후진할 수 없다면 작동을 멈춘다.

3. 현재 칸의 주변 4칸 중 청소되지 않은 빈 칸이 있는 경우,

    1. 반시계 방향으로 90도 회전한다.

    2. 바라보는 방향을 기준을 앞쪽 칸이 청소되지 않은 빈 칸인 경우 한 칸 전진한다.

    3. 1번으로 돌아간다.

---

입력: 첫째 줄에 방의 크기 N과 M이 입력된다. (3 <= N, M <= 50) 둘째 줄에 처음에 로봇 청소기가 있는 칸의 좌표 (r, c)와 처음에 로봇 청소기가 바라보는 방향 d가 입력된다. d가 0일 때 북, 1일때 동, 2일때 남, 3일때 서이다.

셋째 줄부터 N개의 줄에 각 장소의 상태를 나타내는 N * M개의 값이 한 줄에 M개씩 입력된다. i번째 줄의 j번째 값은 칸 (i, j)의 상태를 나타내며, 이 값이 0인 경우 (i, j)가 청소되지 않은 빈 칸이고, 1인 경우 (i, j)에 벽이 있는 것이다. 방의 가장 북쪽, 가장 남쪽, 가장 서쪽, 가장 동쪽 줄 중 하나 이상에 위치한 모든 칸에는 벽이 있다. 로봇 청소기가 있는 칸은 항상 빈 칸이다.

---

 

구현 문제다. 문제가 시키는 대로 하면 된다.

 

import sys
sys.setrecursionlimit(10000000)

di = [0, 1, 0, -1]
dj = [1, 0, -1, 0]

def find_clean_blank(r, c, d):
    if d == 0:
        if 0 <= c-1 < N and arr[r][c-1] == 0:
            return start_clean(r, c-1, 3)
        else:
            return find_clean_blank(r, c, 3)

    elif d == 1:
        if 0 <= r-1 < M and arr[r-1][c] == 0:
            return start_clean(r-1, c, 0)
        else:
            return find_clean_blank(r, c, 0)

    elif d == 2:
        if 0 <= c+1 < N and arr[r][c+1] == 0:
            return start_clean(r, c+1, 1)
        else:
            return find_clean_blank(r, c, 1)

    else: # 서
        if 0 <= r+1 < M and arr[r+1][c] == 0:
            return start_clean(r+1, c, 2)
        else:
            return find_clean_blank(r, c, 2)

def around_4_available(i, j):
    check = False
    for z in range(4):
        ni = i + di[z]
        nj = j + dj[z]
        if 0 <= ni < N and 0 <= nj < M:
            if arr[ni][nj] == 0:
                check = True
                break

    return check

def start_clean(r, c, d):
    global ans
    if arr[r][c] == 0:
        ans += 1
    arr[r][c] = 2
    if around_4_available(r, c):
        return find_clean_blank(r, c, d)
    else:
        if d == 0:
            if 0 <= r + 1 < M and arr[r+1][c] != 1:
                return start_clean(r+1, c, d)
            else:
                return
        elif d == 1:
            if 0 <= c - 1 < N and arr[r][c-1] != 1:
                return start_clean(r, c-1, d)
            else:
                return
        elif d == 2:
            if 0 <= r - 1 < M and arr[r-1][c] != 1:
                return start_clean(r-1, c, d)
            else:
                return
        else:
            if 0 <= c + 1 < N and arr[r][c+1] != 1:
                return start_clean(r, c+1, d)
            else:
                return

N, M = map(int, input().split())
r, c, d = map(int, input().split())
arr = []
for i in range(N):
    arr.append(list(map(int, input().split())))

ans = 0
start_clean(r, c, d)
print(ans)

정직하게 시키는 대로 쭉 구현했다. 그랬더니 메모리초과가 뜬다.

재귀함수의 콜스택이 쌓여 메모리가 초과된 것 같다. 함수를 살짝 수정해 보았다.

import sys
sys.setrecursionlimit(10000000)

di = [0, 1, 0, -1]
dj = [1, 0, -1, 0]

def find_clean_blank(r, c, d):
    d = d
    for i in range(5):
        if d == 0:
            if 0 <= c-1 < N and arr[r][c-1] == 0:
                return start_clean(r, c-1, 3)
            else:
                d = 3

        elif d == 1:
            if 0 <= r-1 < M and arr[r-1][c] == 0:
                return start_clean(r-1, c, 0)
            else:
                d = 0

        elif d == 2:
            if 0 <= c+1 < N and arr[r][c+1] == 0:
                return start_clean(r, c+1, 1)
            else:
                d = 1

        else: # 서
            if 0 <= r+1 < M and arr[r+1][c] == 0:
                return start_clean(r+1, c, 2)
            else:
                d = 2
    return

def around_4_available(i, j):
    check = False
    for z in range(4):
        ni = i + di[z]
        nj = j + dj[z]
        if 0 <= ni < N and 0 <= nj < M:
            if arr[ni][nj] == 0:
                check = True
                break

    return check

def start_clean(r, c, d):
    global ans
    if arr[r][c] == 0:
        ans += 1
    arr[r][c] = 2
    if around_4_available(r, c):
        return find_clean_blank(r, c, d)
    else:
        if d == 0:
            if 0 <= r + 1 < M and arr[r+1][c] != 1:
                return start_clean(r+1, c, d)
            else:
                return
        elif d == 1:
            if 0 <= c - 1 < N and arr[r][c-1] != 1:
                return start_clean(r, c-1, d)
            else:
                return
        elif d == 2:
            if 0 <= r - 1 < M and arr[r-1][c] != 1:
                return start_clean(r-1, c, d)
            else:
                return
        else:
            if 0 <= c + 1 < N and arr[r][c+1] != 1:
                return start_clean(r, c+1, d)
            else:
                return

N, M = map(int, input().split())
r, c, d = map(int, input().split())
arr = []
for i in range(N):
    arr.append(list(map(int, input().split())))

ans = 0
start_clean(r, c, d)
print(ans)

위와 같이 수정한 결과 메모리 초과는 뜨지 않았다. 재귀 부분을 반복문으로 바꾸어주어 메모리 효율이 좋아진 듯 하다.

근데 답이 틀렸다고 나온다.

백준의 질문 게시판에 있는 반례를 모두 집어넣어 봤지만 틀린 부분을 찾지 못했다. 뭐가 문제인걸까?

 

2시간정도 코드를 보다가 문제점을 발견했다. r과 c는 각각 N과 M의 범위와 연관이 있다. 그런데 그 범위를 잘못 써준 부분이 있었다. 중간에 수정을 한번 했는데, 미처 N과 M은 바꿔 써주지 않은 것.

 

import sys
sys.setrecursionlimit(10000000)

di = [0, 1, 0, -1]
dj = [1, 0, -1, 0]

def find_clean_blank(r, c, d):
    d = d
    for i in range(5):
        if d == 0: # 북쪽을 바라보고 있다면
            if 0 <= c-1 < M and arr[r][c-1] == 0: # 반시계 방향으로 90도 돌린 서쪽을 바라보고, 그 칸이 청소 가능한 빈 칸이면
                return start_clean(r, c-1, 3) # 해당 칸의 좌표와 서쪽 데이터를 넣은 후 청소 함수 실행
            else:
                d = 3

        elif d == 1:
            if 0 <= r-1 < N and arr[r-1][c] == 0:
                return start_clean(r-1, c, 0)
            else:
                d = 0

        elif d == 2:
            if 0 <= c+1 < M and arr[r][c+1] == 0:
                return start_clean(r, c+1, 1)
            else:
                d = 1

        else: # 서
            if 0 <= r+1 < N and arr[r+1][c] == 0:
                return start_clean(r+1, c, 2)
            else:
                d = 2
    return

def around_4_available(i, j):
    check = False
    for z in range(4):
        ni = i + di[z]
        nj = j + dj[z]
        if 0 <= ni < N and 0 <= nj < M:
            if arr[ni][nj] == 0:
                check = True
                break

    return check

def start_clean(r, c, d):
    global ans
    if arr[r][c] == 0: # 만약 현재 위치한 칸이 청소하기 전의 빈 칸이라면
        ans += 1 # 청소한 칸 개수 1 증가시키고
    arr[r][c] = 2 # 청소했다는 표시를 세우지
    if around_4_available(r, c): # 청소를 다 한 후 주변 4개의 칸에 빈 칸이 있으면
        return find_clean_blank(r, c, d) # 주변의 4칸중 청소할 칸을 정해주는 함수를 실행시키자
    else:
        if d == 0:
            if 0 <= r + 1 < N and arr[r+1][c] == 2:
                return start_clean(r+1, c, d)
            else:
                return
        elif d == 1:
            if 0 <= c - 1 < M and arr[r][c-1] == 2:
                return start_clean(r, c-1, d)
            else:
                return
        elif d == 2:
            if 0 <= r - 1 < N and arr[r-1][c] == 2:
                return start_clean(r-1, c, d)
            else:
                return
        else:
            if 0 <= c + 1 < M and arr[r][c+1] == 2:
                return start_clean(r, c+1, d)
            else:
                return

N, M = map(int, input().split()) # 로봇 청소기가 돌아야 하는 방의 넓이
r, c, d = map(int, input().split()) # r, c는 로봇 청소기의 좌표, d는 로봇 청소기가 바라보고 있는 방향
arr = [] # 방의 정보가 저장될 리스트
for i in range(N):
    arr.append(list(map(int, input().split()))) # 1은 벽, 0은 청소 가능한 빈 칸

ans = 0 # 청소한 칸의 수
start_clean(r, c, d) # 청소 함수
print(ans)

교훈: 잠올땐 한숨 자고 일어나서 풀자.