로봇 청소기 백준 14503번 구현

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

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

로봇 청소기가 있는 장소는 N×M 크기의 직사각형으로 나타낼 수 있으며, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 벽 또는 빈 칸이다. 청소기는 바라보는 방향이 있으며, 이 방향은 동, 서, 남, 북중 하나이다. 지도의 각 칸은 (r, c)로 나타낼 수 있고, r은 북쪽으로부터 떨어진 칸의 개수, c는 서쪽으로 부터 떨어진 칸의 개수이다.

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

현재 위치를 청소한다. 현재 위치에서 현재 방향을 기준으로 왼쪽방향부터 차례대로 탐색을 진행한다. 왼쪽 방향에 아직 청소하지 않은 공간이 존재한다면, 그 방향으로 회전한 다음 한 칸을 전진하고 1번부터 진행한다. 왼쪽 방향에 청소할 공간이 없다면, 그 방향으로 회전하고 2번으로 돌아간다. 네 방향 모두 청소가 이미 되어있거나 벽인 경우에는, 바라보는 방향을 유지한 채로 한 칸 후진을 하고 2번으로 돌아간다. 네 방향 모두 청소가 이미 되어있거나 벽이면서, 뒤쪽 방향이 벽이라 후진도 할 수 없는 경우에는 작동을 멈춘다. 로봇 청소기는 이미 청소되어있는 칸을 또 청소하지 않으며, 벽을 통과할 수 없다.

---

조건을 따라가는 간단한 시뮬레이션 문제로 보입니다. 벽 그리고 이미 방문한 지점은 가지 못하게 관리를 하면서 주어진 조건에 따라서 진행을 하면 됩니다.

n,m = map(int,input().split())
graph = []
visited = [[0] * m for _ in range(n)]
r,c,d = map(int,input().split())

for _ in range(n):
    graph.append(list(map(int,input().split())))
    
#조건에 따라 d가 0 북, 1 동,2 남,3 서
dx = [-1,0,1,0]
dy = [0,1,0,-1]

조건에 따라서 입력을 받습니다. 우리가 필요한 지도와 방문을 체크하기 위한 그래프 마지막으로 동서남북 이동 방향을 결정할 dx, dy를 정해줍니다.

# 처음 시작하는 곳 방문 처리
visited[r][c] = 1
count = 1

그리고 처음 시작의 초기화를 해줍시다. 일단 로봇청소기가 놓이는 곳은 방문과 청소가 이루어졌습니다. 청소를 1회 했네요

while True:
    flag = 0
    # 4방향 확인
    for _ in range(4):
        # 0,3,2,1 순서 만들어주기위한 식
        d = (d+3)%4
        nx = r + dx[d]
        ny = c + dy[d]
        if 0 <= nx < n and 0 <= ny < m and graph[nx][ny] == 0 and visited[nx][ny] == 0:
            visited[nx][ny] = 1
            count += 1
            r = nx
            c = ny
            #청소 한 방향이라도 했으면 다음으로 넘어감
            flag = 1
            break
    if flag == 0: # 4방향 모두 청소가 되어 있을 때,
        if graph[r-dx[d]][c-dy[d]] == 1: #후진했는데 벽
            print(count)
            break
        else:
            r,c = r-dx[d],c-dy[d]

코드를좀 쪼개서 보겠습니다.

for _ in range(4):
        # 0,3,2,1 순서 만들어주기위한 식
        d = (d+3)%4
        nx = r + dx[d]
        ny = c + dy[d]

방향을 4곳으로 하는 것을 알겠는데 왜 시작하자마자 3을 더하고 4의 나머지를 하는 이유는 다음 조건 때문입니다.

• 현재 위치에서 현재 방향을 기준으로 왼쪽방향부터 차례대로 탐색을 진행한다.

왼쪽 방향에 아직 청소하지 않은 공간이 존재한다면, 그 방향으로 회전한 다음 한 칸을 전진하고 1번부터 진행한다. 일단 순서는 북동남서 시계방향으로 되어 있는데 현재 방향을 기준으로 왼쪽 방향부터 차례대로 탐색을 진행합니다.

즉 북쪽을 보고 있으면 서쪽을 동쪽을보고 있으면 북쪽을 이렇게 자기 위치에서 반시계 방향으로 한칸 돈곳을 먼저 시작을 하는데 여기가 바로 3을 더하고 4의 나머지가 됩니다.

if 0 <= nx < n and 0 <= ny < m and graph[nx][ny] == 0 and visited[nx][ny] == 0:
	visited[nx][ny] = 1
    count += 1
    r = nx
    c = ny
    #청소 한 방향이라도 했으면 다음으로 넘어감
    flag = 1
    break

그리고 이동한 nx가 범위를 벗어나지 않으며 벽이 아닐 경우 마지막으로 방문하지 않았을 경우에 청소를 시작합니다.

해당 노드를 방문처리 해주고, count를 1올리고 청소기의 위치를 새로 갱신을 합니다. 하지만 한번에 모든 방향을 청소 하는 것이아니라 왼쪽으로 돌다가 청소를 한번이라도 하면 넘어가기 때문에 break로 탈출을 하고 flag로 청소 했다는 표식을 남깁니다.

if flag == 0: # 4방향 모두 청소가 되어 있을 때,
        if graph[r-dx[d]][c-dy[d]] == 1: #후진했는데 벽
            print(count)
            break
        else:
            r,c = r-dx[d],c-dy[d]

4방향 모두 청소가 완료됬다면 한칸 후진을 합시다. 전진할때 반대로 빼면 됩니다. 이때 벽을 만난다면 count를 출력하고 종료를 하고 벽이 아니라면 다시 거기서부터 진행을 하게 됩니다.