[백준] 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로도 풀어보자.