[백준] 14503 : 로봇 청소기 - Python

문제

있는 그대로 구현하면 되는 문제.

내 코드

import sys

sys.stdin = open("input.txt", "rt")
sys.setrecursionlimit(10**8)

n,m = map(int, input().split())
nowX,nowY, direction, = map(int, input().split()) # ! 현재 로봇 좌표, 방향
g = [list(map(int, input().split())) for _ in range(n)]
# ! (0,0) -> (n-1,m-1) 로 이동하기

up, right, down, left = 0,1,2,3

# ! 청소하지 않은 칸 : 0 벽 : 1

dx = [-1,0,1,0]
dy = [0,1,0,-1]
cnt = 0

def DFS(x,y):
    global cnt, direction
    global nowX, nowY

    # ! step1
    if g[x][y] == 0:
        g[x][y] = 2 # ! 방 청소 처리
        cnt += 1
    flag = False
    d = direction
    for i in range(4): # ! 반시계방향으로 돌면서 확인
        d = (d + 3) % 4
        nx = x + dx[d]
        ny = y + dy[d]
        if 0<=nx<n and 0<=ny<m and g[nx][ny] == 0:
            flag = True
            break

    # ! d에 대해서 실행.
    if flag:
        direction = d
        nx = x + dx[direction]
        ny = y + dy[direction]
        if 0<=nx<n and 0<=ny<m and g[nx][ny] == 0:
            DFS(nx,ny)
        else:
            DFS(x,y)
    else: # ! 이동 불가능 -> 여기서는 그냥 빈칸도 이동 가능
        nx = x - dx[direction]
        ny = y - dy[direction]
        if 0<=nx<n and 0<=ny<m and g[nx][ny] != 1:
            DFS(nx,ny) # ! 후진
        else:
             return # ! 후진 안되면 끝.

DFS(nowX, nowY)
print(cnt)

코멘트

규칙에 따라 로봇 청소기를 움직이고, 이때 로봇 청소기가 청소한 공간을 모두 더해주면 된다.

그대로 코드로 구현하는 것이 어려울 수 있다.
-> 바로 코딩을 진행하기 보다는 도식을 그려서 아니면 직접 좌표 하나 그리고 그 위에서 움직여보여 확실히 머릿속에 이해를 하고 코딩을 해야지만 시간이 짧아진다.

문제에서 주어진 조건대로 이동 가능한지 판단.
주어진 반시계 방향 테크닉을 효과적으로 활용하기 위해 dx, dy를 1씩 감소시킬 때마다 좌회전이 되도록 주어진 북동남서 순으로 저장.

• 왼쪽으로 회전한다는 것은 dx,dy값을 3씩 증가시켜주어야 한다는 것.

이미 해당 칸에 방문했는지에 대한 여부가 중요한 문제.

후진할 때는 굳이 청소했는지 안했는지 따지지 않고 벽만 아니면 가능.

삼성 옛날 구현은 있는 그대로 "진짜 하라는 대로 해라" 그러니까 직접 해보면서 그려보면서 실행해봐야 한다.

BFS로도 풀어보자.

BFS

import sys
sys.stdin = open("input.txt", "rt")
from collections import deque
# 로봇 청소기와 방의 상태 주어짐 -> 청소하는 영역의 개수 구하기
# n,m 크기, 각각의 칸은 벽 또는 빈  (청소되지 않은 칸)
# 로봇 청소기 동작 조건
# 1. 현재 칸이 청소되지 않은 경우 현재 칸 청소
# 2. 현재 칸의 주변 4칸 중 청소되지 않은 빈 칸이 없는 경우
# 2-1. 바라보는 방향 유지한 채로 한 칸 후진 가능 -> 한 칸 후진하고 1번으로 돌아감
# 2-2. 바라보는 방향의 뒤쪽 칸이 벽이라 후진할 수 없다면 동작 멈춤
# 3. 현재 칸의 주변 4칸 중 청소되지 않은 빈칸이 있는 경우
# 3-1. 반 시계 90도 회전
# 3-2. 바라보는 방향 기준 앞쪽 청소 X -> 바라보는 방향으로 한 칸 전진
# 3-3. 1번으로 돌아감.
# --> 반복적, 로봇 청소기가 멈출 때까지 청소하는 칸의 개수

n,m = map(int, input().split())
startX, startY, dir = map(int, input().split()) # 청소기 시작 위치(x,y), 방향
g = [list(map(int, input().split())) for _ in range(n)]
# 0 빈칸, 1 벽

dx = [-1,0,1,0]
dy = [0,1,0,-1] # 북, 동, 남, 서
cnt = 0
visited = [[False] * m for _ in range(n)]  # 이 문제의 경우 방문처리 필요

def isInner(x,y):
    return 0<=x<n and 0<=y<m

def step2(x,y): # 현재 칸 기준 빈칸 존재??
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if isInner(nx,ny) and g[nx][ny] == 0 and not visited[nx][ny]: # 빈칸 존재
            return False
    else: # 청소하지 않은 빈칸 없음
        return True

dq = deque()
def bfs(startX,startY, dir):
    global cnt
    dq.append((startX,startY,dir)) # 초기 위치, 초기 방향

    while dq:
        x,y,d = dq.popleft() # 로봇청소기의 현재 위치(x,y) , 방향:d
        if g[x][y] == 0 and not visited[x][y]: # step1. 현재 칸 빈칸 ?
            visited[x][y] = True # 방문 처리
            cnt += 1
        if step2(x,y): # 현재 칸 주변 4칸 빈칸 없어 ?
            direction = (d+2) % 4 # 뒤로 이동할 방향
            nx = x + dx[direction]
            ny = y + dy[direction]
            if isInner(nx,ny) and g[nx][ny] == 0: # 후진 가능 (방문했는지는 신경 X)
                dq.append((nx,ny,d)) # 방향은 유지
            else:
                break # 이동 불가능하면 멈춤
        else: # 현재 칸 기준 주변 4칸 빈칸 존재
            direction = (d + 3) % 4 # 반시계 방향 회전.
            nx = x + dx[direction]
            ny = y + dy[direction]
            if isInner(nx,ny) and g[nx][ny] == 0 and not visited[nx][ny]: # 바라보는 방향 기준 앞쪽 칸이 청소되지 않은 빈칸인 경우 전진
                visited[nx][ny] = True # 방문 처리
                cnt += 1
                dq.append((nx,ny,direction)) # 방향 변경해서..
            else: # 빈칸이 아니라면 1번으로 돌아감 --> 여기 조건을 만족하지 못했음. 즉 제자리에서 방향만 바뀌었어야 함.
                dq.append((x,y,direction))

bfs(startX,startY,dir)
print(cnt)

피드백

3번 조건 처리에서 문제가 있었음.
조건에서 반시계 90도 회전 후 바라보는 방향 기준 앞쪽 칸이 청소되지 않은 빈칸이면 한 칸 전진. -> 이 조건은 잘 처리했지만,
빈칸이 아니라면, 방향만 바꾸고 현재위치를 큐에 넣었어야 했음 !
-> 회전만 하고 전진을 안할 수 있었음. 문제를 잘 해석했어야 했다.

암기할 만한 정형화 패턴들

오랜만에 문제를 푸니, 정형화된 패턴은 암기를 진행하자.

1. 방향처리

dx = [-1,0,1,0]
dy = [0,1,0,-1]  # 북, 동, 남, 서

# 반시계 회전: (d + 3) % 4
# 시계 회전: (d + 1) % 4  
# 반대 방향: (d + 2) % 4

2. 범위 체크 함수

def isInner(x,y):
    return 0<=x<n and 0<=y<m

문제를 풀면서, 빡구현의 경우 함수 분리를 잘 하자.
그리고 만약 원하는 대로 흘러가지 않은 경우, 출력을 해보자. 내가 생각하는 대로 출력이 되는지 판단이 필요.

물론 이 문제는 함수명을 BFS로 할 게 아니라, 단순 시뮬레이션임.