[BOJ] 14503. 로봇 청소기

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

14503번: 로봇 청소기

 

 

1. 해결방법

"""
1. 아이디어
- while문을 사용해서 특정 조건이 끝날 떄, 루프를 해제
- while문 안에 for문을 사용해서 동서남북을 체크
- for문으로 체크가 안되거나 완료 시, 보는 방향을 그대로 하고 뒤로 후진

2. 시간복잡도
- O(NM) : 50^2

3. 자료구조
- 2차원 배열 : graph[][]
- 청소가 안된 빈 칸 : 0, 벽 : 1, 청소가 완료된 칸 : 2
"""

 

 

2. 정답코드

입력 예제(1)

3 3
1 1 0
1 1 1
1 0 1
1 1 1

출력 예제(1)

1

 

입력 예제(2)

11 10
7 4 0
1 1 1 1 1 1 1 1 1 1
1 0 0 0 0 0 0 0 0 1
1 0 0 0 1 1 1 1 0 1
1 0 0 1 1 0 0 0 0 1
1 0 1 1 0 0 0 0 0 1
1 0 0 0 0 0 0 0 0 1
1 0 0 0 0 0 0 1 0 1
1 0 0 0 0 0 1 1 0 1
1 0 0 0 0 0 1 1 0 1
1 0 0 0 0 0 0 0 0 1
1 1 1 1 1 1 1 1 1 1

출력 예제(2)

57

 

코드

import sys
input = sys.stdin.readline


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

graph = [list(map(int, input().split())) for _ in range(N)]
answer = 0
dy = [-1, 0, 1, 0]
dx = [0, 1, 0, -1]

# simulate
def simulate(y, x):
    global answer, d

    # 1, 2 반복문
    while True:
        # 1. 현재 위치를 청소한다.
        if graph[y][x] == 0:
            graph[y][x] = 2
            answer += 1
        sw = False

        # 2. 현재 위치에서 다음을 반복하면서 인접한 칸을 탐색한다.
        for i in range(1, 5):
            # 왼쪽 방향으로 회전
            ny, nx = y + dy[d - i], x + dx[d - i]
            if 0 <= ny < N and 0 <= nx < M:
                # 현재 위치의 바로 왼쪽에 아직 청소하지 않은 빈 공간이 존재한다면
                # if문 동작 시, 다시 1번부터 동작
                if graph[ny][nx] == 0:
                    y, x = ny, nx
                    d = (d - i + 4) % 4
                    sw = True
                    break

        # 연속으로 네 번 실행되었을 경우
        if sw == False:
            # 뒤가 막혀있는지 확인
            ny, nx = y - dy[d], x - dx[d]
            if 0 <= ny < N and 0 <= nx < M:
                # 벽이라면, 종료
                if graph[ny][nx] == 1:
                    break
                # 한 칸 후진
                else:
                    y, x = ny, nx
            else:
                break


# main
simulate(r, c)
print(answer)

ㄲ