[python] 백준 - 14503. 로봇 청소기 (삼성 SW 역량 테스트 기출 문제)

출처 : BACKJOON ONLINE JUDGE

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

14503번: 로봇 청소기

 

문제 요약

1(벽)과 0(청소가능)으로 구성 된 2차원 배열에 로봇 청소기 한대가 놓여있다. 로봇청소기는 바라보고 있는 방향이 있으며 벽을 제외한 인접한 네방향으로 이동할 수 있다. 로봇 청소기가 이동하며 청소한 구역의 수를 구하는 문제

 

 ※ 특별한 알고리즘 없이 제시된 상황을 구현하는 문제이다.

 

1. 입력

sero, garo = map(int, input().split())  # n, m
x, y, direction = map(int, input().split())  # r, c, d
field = [list(map(int, input().split())) for _ in range(sero)]

 

2. 방향설정

문제에서 제시된 것과 같이 북 동 남 서로 방향을 잡았다.

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

 

3. 청소와 이동

바라보고 있는 방향에서 왼쪽부터 차례로 탐색하며, 청소한 곳이 있을 때와 모든 방향 탐색이 끝난 뒤 청소한 곳이 없을 때로 나눠준다.

- 청소가 가능 할 때 -

청소 count 는 1부터 시작하며, 청소가 가능한 곳으로 이동할 때 count 를 +1 씩 더해준다.

청소가 끝난 곳은 청소가 가능한 곳과 구별할 수 있도록 기존의 값인 0에서 2로 바꿔준다.

- 네 방향에 더 이상 청소할 곳이 없을 때 -

뒤쪽 방향이 벽이 아니라면 한칸 후진한다.

뒤쪽 방향이 벽이라면 더 이상 움직일 수 없다. (끝)

cnt = 1
while True:
    field[x][y] = 2  # 청소가 끝난 곳
    for k in range(direction-1, direction-1-4, -1):  # 왼쪽 방향부터 탐색하므로 현재방향-1 부터 시작해서 네번 탐색
        k += 4  # 계산하기 쉽게 (-)인덱스를 (+)인덱스로 바꿔준다.
        if k > 3:
            k = k % 4

        nx = x + dx[k]
        ny = y + dy[k]
        # 청소할 곳이 있을 때
        if field[nx][ny] == 0:
            x = nx  # 청소 할 곳으로 이동
            y = ny
            direction = k  # 바라보는 방향을 움직인 방향으로 바꿔준다.
            cnt += 1  # 청소 하고 카운트 + 1
            break

    else:
        # 모든 방향에 더 이상 청소할 곳이 없을 때
        nx = x - dx[direction]
        ny = y - dy[direction]
        # 후진 할 곳이 있을 때
        if field[nx][ny] != 1:
            x = nx
            y = ny
        # 후진 할 곳이 없을 때
        else:
            break

 

4. 전체코드

sero, garo = map(int, input().split())  # n, m
x, y, direction = map(int, input().split())  # r, c, d
field = [list(map(int, input().split())) for _ in range(sero)]

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

cnt = 1
while True:
    field[x][y] = 2  # 청소가 끝난 곳
    for k in range(direction-1, direction-1-4, -1):  # 왼쪽 방향부터 탐색하므로 현재방향-1 부터 시작해서 네번 탐색
        k += 4  # 계산하기 쉽게 (-)인덱스를 (+)인덱스로 바꿔준다.
        if k > 3:
            k = k % 4

        nx = x + dx[k]
        ny = y + dy[k]
        # 청소할 곳이 있을 때
        if field[nx][ny] == 0:
            x = nx  # 청소 할 곳으로 이동
            y = ny
            direction = k  # 바라보는 방향을 움직인 방향으로 바꿔준다.
            cnt += 1  # 청소 하고 카운트 + 1
            break

    else:
        # 모든 방향에 더 이상 청소할 곳이 없을 때
        nx = x - dx[direction]
        ny = y - dy[direction]
        # 후진 할 곳이 있을 때
        if field[nx][ny] != 1:
            x = nx
            y = ny
        # 후진 할 곳이 없을 때
        else:
            break
    # for i in field:
    #     print(i)
    # print()
print(cnt)