113. [삼성기출9]Python 백준 14503 번 로봇 청소기 자세한 설명

안녕하세요 코딩하는 덕구입니다.

백준 14503 번 로봇 청소기 입니다.

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

14503번: 로봇 청소기

 

먼저 백준 14503 번 로봇 청소기 파이썬 정답 코드입니다. 설명은 아래에 있습니다.

N, M = map(int, (input().split()))
r, c, d = map(int, (input().split())) #r, c 는 좌표
#d는 방향 0 : 북, 1 : 동, 2 : 남, 3 : 서
dir_x = [-1, 0, 1, 0]
dir_y = [0, 1, 0, -1]
room = [] #0 : not cleand, 1 : wall, 2 : cleaned
stack = [(r, c)]
for _ in range(N):
    room.append(list(map(int, input().split())))

def move_rear(x, y, d):
    nd = (d + 2) % 4
    nx = x + dir_x[nd]
    ny = y + dir_y[nd]
    return nx, ny

def turn_left(d):
    return (d + 3) % 4

def need_clean(x, y):
    for i in range(4):
        nx = x + dir_x[i]
        ny = y + dir_y[i]
        if 0 <= nx < N and 0 <= ny < M and room[nx][ny] == 0:
            return True
    return False

def move_forward(x, y, d):
    nx = x + dir_x[d]
    ny = y + dir_y[d]
    return nx, ny

def clean_room():
    global d
    ans = 0

    while stack: #dfs
        x, y = stack.pop()
        if room[x][y] == 0:
            ans += 1
            room[x][y] = 2

        if need_clean(x, y): #주변 청소 가능하면
            for _ in range(4):
                d = turn_left(d) #회전
                nx = x + dir_x[d]
                ny = y + dir_y[d]

                if 0 <= nx < N and 0 <= ny < M and room[nx][ny] == 0:
                    stack.append((nx, ny))
                    break

        else: #청소 불가능 하면
            nx, ny = move_rear(x, y, d) #후진
            if nx < 0 or nx >= N or ny < 0 or ny >= M or room[nx][ny] == 1:
                return ans
            stack.append((nx, ny))

    return ans

print(clean_room())

 

문제 요약

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

1. 현재 칸이 아직 청소되지 않은 경우, 현재 칸을 청소한다.
2. 현재 칸의 주변 4칸 중 청소되지 않은 빈 칸이 없는 경우,
   1. 바라보는 방향을 유지한 채로 한 칸 후진할 수 있다면 한 칸 후진하고 1번으로 돌아간다.
   2. 바라보는 방향의 뒤쪽 칸이 벽이라 후진할 수 없다면 작동을 멈춘다.
3. 현재 칸의 주변 4칸 중 청소되지 않은 빈 칸이 있는 경우,
   1. 반시계 방향으로 90∘회전한다.
   2. 바라보는 방향을 기준으로 앞쪽 칸이 청소되지 않은 빈 칸인 경우 한 칸 전진한다.
   3. 1번으로 돌아간다.

이때 로봇 청소기와 방의 상태가 주어졌을 때 청소하는 범위를 출력하면 됩니다. 

 

문제 접근

가장 최근의 위치에서 2 가지의 조건에 따라 로봇의 행동이 달라지므로, stack을 통해 구현했습니다.

글을 쓰면서 생각났는데, 사실 stack이 아니라 좌표를 담을 변수 하나만 있으면 되겠네요

그리고 문제를 꼼꼼하게 잘 읽으셔야 됩니다.

 

로봇청소기 조건 중

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

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

 

바로 앞에 청소가 가능할지라도 일단 회전해야 된다는 의미입니다.

 

Python 코드 구현

먼저 방의 정보, 로봇의 좌표, 상태를 입력받습니다.

N, M = map(int, (input().split()))
r, c, d = map(int, (input().split())) #r, c 는 좌표

room = [] #0 : not cleand, 1 : wall, 2 : cleaned

for _ in range(N):
    room.append(list(map(int, input().split())))

 

이후 로봇의 좌표를 저장할 stack과  로봇의 이동을 구현하기 위한 리스트들을 구현합니다.

stack = [(r, c)]

#d는 방향 0 : 북, 1 : 동, 2 : 남, 3 : 서
dir_x = [-1, 0, 1, 0]
dir_y = [0, 1, 0, -1]

 

로봇의 이동을 구현해보겠습니다.

앞으로 이동입니다.

현재 좌표와 방향을 입력받고, 해당 방향으로 한칸 이동한 좌표를 출력합니다.

def move_forward(x, y, d):
    nx = x + dir_x[d]
    ny = y + dir_y[d]
    return nx, ny

 

뒤로 이동입니다.

현재 좌표와 방향을 입력받고, 뒤로 한칸 이동한 좌표를 출력합니다. 

d의 범위가 4이상으로 넘어설 수 있으므로 %4를 통해 overflow를 방지합니다.

def move_rear(x, y, d):
    nd = (d + 2) % 4
    nx = x + dir_x[nd]
    ny = y + dir_y[nd]
    return nx, ny

  

로봇의 방향전환입니다. 왼쪽으로만 돌 수 있습니다.

d= d-1 이지만 d가 음수가 될 수 있으므로, (d+3)%4를 해주었습니다.

def turn_left(d):
    return (d + 3) % 4

 

로봇 주변에 청소할 곳이 있는지 찾는 함수입니다.

동, 서, 남, 북이 room 범위 안에 있고, 청소하지 않은 상태면 True 를 출력합니다.

만약 주변에 청소할 곳이 없다면 False를 출력합니다.

def need_clean(x, y):
    for i in range(4):
        nx = x + dir_x[i]
        ny = y + dir_y[i]
        if 0 <= nx < N and 0 <= ny < M and room[nx][ny] == 0:
            return True
    return False

 

이제 핵심코드입니다. 방 청소를 시작해봅시다.

방향을 구현하기 위해 d를 전역변수로 사용하고, 출력할 정답값을 초기화 합니다.

global d
ans = 0

 

dfs와 비슷한 방식으로 동작합니다.

스텍에 좌표가 있다면 출력해서 좌표를 입력받고, 해당 좌표가

청소하기 전이면 청소하고, ans를 1 늘려줍니다.

while stack: #dfs
    x, y = stack.pop()
    if room[x][y] == 0:
        ans += 1
        room[x][y] = 2

 

이후 주변 청소가 가능한지 확인합니다.

1. 청소가 가능하면 회전시키고, 회전한 방향으로 한칸 앞이 청소 전이라면

stack.append를 통해 해당 좌표로 이동합니다.

if need_clean(x, y): #주변 청소 가능하면
    for _ in range(4):
        d = turn_left(d) #회전
        nx = x + dir_x[d]
        ny = y + dir_y[d]

        if 0 <= nx < N and 0 <= ny < M and room[nx][ny] == 0:
            stack.append((nx, ny))
            break

 

2. 청소가 불가능하면

후진합니다.

이때 벽에 가로막혀 후진이 불가능하면 청소를 종료하고 답을 출력합니다.

후진이 가능하면 다시 해당 좌표로 이동해 청소 알고리즘을 반복합니다.

else: #청소 불가능 하면
    nx, ny = move_rear(x, y, d) #후진
    if nx < 0 or nx >= N or ny < 0 or ny >= M or room[nx][ny] == 1:
        return ans
    stack.append((nx, ny))

return ans

 

파이썬 백준 14503 번 로봇 청소기 최종 코드입니다. 

N, M = map(int, (input().split()))
r, c, d = map(int, (input().split())) #r, c 는 좌표
#d는 방향 0 : 북, 1 : 동, 2 : 남, 3 : 서
dir_x = [-1, 0, 1, 0]
dir_y = [0, 1, 0, -1]
room = [] #0 : not cleand, 1 : wall, 2 : cleaned
stack = [(r, c)]
for _ in range(N):
    room.append(list(map(int, input().split())))

def move_rear(x, y, d):
    nd = (d + 2) % 4
    nx = x + dir_x[nd]
    ny = y + dir_y[nd]
    return nx, ny

def turn_left(d):
    return (d + 3) % 4

def need_clean(x, y):
    for i in range(4):
        nx = x + dir_x[i]
        ny = y + dir_y[i]
        if 0 <= nx < N and 0 <= ny < M and room[nx][ny] == 0:
            return True
    return False

def move_forward(x, y, d):
    nx = x + dir_x[d]
    ny = y + dir_y[d]
    return nx, ny

def clean_room():
    global d
    ans = 0

    while stack: #dfs
        x, y = stack.pop()
        if room[x][y] == 0:
            ans += 1
            room[x][y] = 2

        if need_clean(x, y): #주변 청소 가능하면
            for _ in range(4):
                d = turn_left(d) #회전
                nx = x + dir_x[d]
                ny = y + dir_y[d]

                if 0 <= nx < N and 0 <= ny < M and room[nx][ny] == 0:
                    stack.append((nx, ny))
                    break

        else: #청소 불가능 하면
            nx, ny = move_rear(x, y, d) #후진
            if nx < 0 or nx >= N or ny < 0 or ny >= M or room[nx][ny] == 1:
                return ans
            stack.append((nx, ny))

    return ans

print(clean_room())

 

제가 운영하는 오픈 카톡방입니다. 알고리즘, 코딩, 취업정보 등 자유롭게 질문, 답변 및 대화 나눠요.

https://open.kakao.com/o/guGhqGAg

알고리즘, 코딩, 개발자 취업 질문방 (비번 4321)

 

백준 14503 번 로봇 청소기 자세한 설명 및 Python 코드였습니다.

감사합니다.