백준 14503번 : 로봇 청소기

Python을 이용한 14503번 : 로봇 청소기에 대해서 포스팅하겠습니다. 14503번은 구현문제로서 골드난이도이지만 쉽게 풀 수 있습니다.

Table of Contents

14503번 문제설명

첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다.
단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다.
정점 번호는 1번부터 N번까지이다.

14503번 접근방법

1. 입력 데이터 구조

n, m : 방의 크기를 나타내는 정수 (NxM 직사각형)
r, c, d : 로봇 청소기의 초기 위치(r, c)와 바라보는 방향(d)
maps : 방의 상태를 나타내는 2차원 배열, 0은 빈 칸, 1은 벽을 의미

2. 알고리즘 설명

초기 설정
- 방의 크기(n x m), 로봇 청소기의 초기 위치(r, c)와 바라보는 방향(d)를 입력받습니다.
- 방의 상태를 나타내는 maps 배열을 초기화합니다. 여기서 0은 청소하지 않은 빈 칸, 1은 벽을 나타냅니다.
- 이동 방향(rotation) 배열은 로봇이 북, 동, 남, 서 방향으로 이동할 때 사용됩니다.
청소 진행
- 로봇 청소기는 현재 위치에서 청소를 시작합니다. 현재 칸이 청소되지 않았다면, 청소를 하고 청소한 칸의 수(count)를 증가시킵니다.
- 청소한 위치는 -1로 표시하여, 나중에 이 위치가 청소된 상태임을 알 수 있습니다.
주변 상황 판단
- blank_check 함수는 현재 위치 주변의 4칸을 확인하고, 청소할 수 있는 빈 칸이 있는지 검사합니다.
- 만약 주변에 청소할 빈 칸이 없다면, 로봇은 후진을 시도합니다. 이 때, 뒤쪽 칸이 벽이 아니라면 후진하고, 벽이라면 작동을 멈춥니다.
방향 전환과 이동
- 주변에 청소할 빈 칸이 있다면, 로봇은 반시계 방향으로 90도 회전합니다(d = (d - 1) % 4).
- 회전한 후에, 로봇은 새로운 방향으로 전진을 시도합니다. 이동할 칸이 청소되지 않은 빈 칸이면 전진합니다.
반복 실행
- 위의 과정을 반복하여 로봇이 더 이상 움직일 수 없을 때까지 청소 영역을 확장합니다. 이는 로봇이 벽에 막혀 후진할 수 없는 경우에 해당합니다.
결과 출력
- 로봇이 청소를 마치면, 청소한 칸의 총 수를 출력합니다.

3. 14503번 코드

Python

# https://www.acmicpc.net/problem/14503
from sys import stdin

# 방의 크기(N, M)을 입력받음
n, m = map(int, stdin.readline().split())
# 로봇 청소기의 초기 위치(r, c)와 바라보는 방향(d)를 입력받음
r, c, d = map(int, stdin.readline().split())
# 방의 상태를 나타내는 지도 정보를 입력받음
maps = [list(map(int, stdin.readline().split())) for i in range(n)]

# 로봇 청소기의 이동 방향을 정의 (북, 동, 남, 서 순서)
rotation = [(-1, 0), (0, 1), (1, 0), (0, -1)]

# 주변 4칸 중 청소할 수 있는 빈 칸이 있는지 확인하는 함수
def blank_check(r, c, maps):
    for x, y in rotation:
        nx, ny = r + x, c + y
        if 0 <= nx < n and 0 <= ny < m and maps[nx][ny] == 0:
            return False
    return True

# 청소한 칸의 수를 세는 변수
count = 0

# 로봇 청소기 작동 시작
while True:
    if maps[r][c] == 0:  # 현재 위치가 청소되지 않았다면 청소
        count += 1
        maps[r][c] = -1  # 청소한 위치는 -1로 표시

    if blank_check(r, c, maps):  # 주변에 청소할 수 있는 칸이 없으면
        x, y = rotation[(d + 2) % 4]  # 현재 바라보는 방향의 반대 방향으로 이동
        nx, ny = x + r, y + c
        if maps[nx][ny] != 1:  # 뒤쪽이 벽이 아니라면 후진
            r, c = nx, ny
        else:
            break  # 뒤쪽이 벽이라면 작동을 멈춤

    else:  # 주변에 청소할 수 있는 칸이 있으면
        d = (d - 1) % 4  # 반시계 방향으로 90도 회전
        x, y = rotation[d]
        nx, ny = x + r, y + c
        if maps[nx][ny] == 0:  # 앞쪽 칸이 청소되지 않은 빈 칸이면 전진
            r, c = nx, ny

# 청소한 칸의 개수를 출력
print(count)

14503번 문제설명

14503번 접근방법

1. 입력 데이터 구조

2. 알고리즘 설명

3. 14503번 코드

Related posts:

댓글 달기 댓글 취소