백준 14503번: 로봇 청소기 (G5) - Python 풀이

문제 설명

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

로봇 청소기가 있는 방은 N × M 크기의 직사각형으로 나타낼 수 있으며, 1 × 1 크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 벽 또는 빈 칸이다. 청소기는 바라보는 방향이 있으며, 이 방향은 동, 서, 남, 북 중 하나이다. 방의 각 칸은 좌표 (r, c)로 나타낼 수 있고, 가장 북쪽 줄의 가장 서쪽 칸의 좌표가 (0, 0), 가장 남쪽 줄의 가장 동쪽 칸의 좌표가 (N-1, M-1)이다. 즉, 좌표 (r, c)는 북쪽에서 (r+1)번째에 있는 줄의 서쪽에서 (c+1)번째 칸을 가리킨다. 처음에 빈 칸은 전부 청소되지 않은 상태이다.

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

1번) 현재 칸이 아직 청소되지 않은 경우, 현재 칸을 청소한다.
2번) 현재 칸의 주변 4칸 중 청소되지 않은 빈 칸이 없는 경우,
1번) 바라보는 방향을 유지한 채로 한 칸 후진할 수 있다면 한 칸 후진하고 1번으로 돌아간다.
2번) 바라보는 방향의 뒤쪽 칸이 벽이라 후진할 수 없다면 작동을 멈춘다.
3번) 현재 칸의 주변 4칸 중 청소되지 않은 빈 칸이 있는 경우,
1번) 반시계 방향으로 90도 회전한다.
2번) 바라보는 방향을 기준으로 앞쪽 칸이 청소되지 않은 빈 칸인 경우 한 칸 전진한다.
3번) 1번으로 돌아간다.

입력

첫째 줄에 방의 크기 N과 M이 입력된다. (3 ≤ N, M ≤ 50)  둘째 줄에 처음에 로봇 청소기가 있는 칸의 좌표 (r, c)와 처음에 로봇 청소기가 바라보는 방향 d가 입력된다. d가 0인 경우 북쪽, 1인 경우 동쪽, 2인 경우 남쪽, 3인 경우 서쪽을 바라보고 있는 것이다.

셋째 줄부터 N개의 줄에 각 장소의 상태를 나타내는 N × M개의 값이 한 줄에 M개씩 입력된다. i번째 줄의 j번째 값은 칸 (i, j)의 상태를 나타내며, 이 값이 0인 경우 (i, j)가 청소되지 않은 빈 칸이고, 1인 경우 (i, j)에 벽이 있는 것이다. 방의 가장 북쪽, 가장 남쪽, 가장 서쪽, 가장 동쪽 줄 중 하나 이상에 위치한 모든 칸에는 벽이 있다. 로봇 청소기가 있는 칸은 항상 빈 칸이다.

출력

로봇 청소기가 작동을 시작한 후 작동을 멈출 때까지 청소하는 칸의 개수를 출력한다.

예제 입력 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

풀이 과정

구현 문제입니다.

사실 별로 어려운 문제는 아닌데, 문제 해석하는 것이 좀 걸리는 문제입니다.

저의 경우... 그냥 문제를 그대~로 코드로 옮겼더니 맞은 아마도 별로 좋지 않은 코드로 풀었습니다!

스터디에서 시간 재고 와랄라 푼 거라

흠 지금 고칠 수 있다면 rotate 함수를 좀 더 깔쌈하게 

return (d-1) % 4 로 적을 수 있을 것 같습니다.

그리고 저는 이 문제 풀 때 예전에 프로그래머스에서 푼... 집이랑 호수? 나오는 문제였는데
아무튼 그 문제 풀었을 때가 생각이 나서

벽(해당 문제에서의 1)을 쉽게 처리하려고 청소해야 하는 방 데이터를 가진 배열의 상하좌우를 감싸는 벽을 만들었습니다.

정답 코드

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

# 방 정보 저장할 2차원 배열
# 상단에 1 벽을 세움
spaces = [[1 for _ in range(M+2)] for _ in range(N+2)]

# 방 정보 채우기
# 좌우에 1 벽을 세움
for i in range(1, N+1):
    spaces[i] = [1] + list(map(int, input().split())) + [1]
# 하단에 1 벽을 세움
spaces[i+1] = [1 for _ in range(M+2)]
# 인덱스 맞추기 위해 +1씩
r+=1
c+=1

# 반시계 방향으로 90도 회전을 구현
# 0을 3, 1을 0, 2를 1, 3을 2로 만드는 함수
def rotate(d):
    d -= 1
    if d == -1:
        d = 3
    return d

# 현재 위치해 있는 (r,c) 좌표가 1이면 종료됨
while spaces[r][c] != 1:
	# 빈 칸이면
    if spaces[r][c] == 0:
    	# 청소 -> -1로 표시
        spaces[r][c] = -1
    # 상하좌우 4군데 중 1개라도 빈 칸이 있으면
    if spaces[r-1][c] == 0 or spaces[r][c-1] == 0 or spaces[r+1][c] == 0 or spaces[r][c+1] == 0:
        # 반시계 방향으로 90도 회전
        d = rotate(d)
		
        # 바라보는 방향을 기준으로 
        for _ in range(4): # 상하좌우 반복이라서 4번 반복
            if d == 0:
            	# 앞쪽 칸이 청소되지 않은 빈 칸인 경우 한 칸 전진
                if spaces[r-1][c] == 0:
                    r -= 1
                    break
                # 바라보는 방향을 기준으로 앞쪽 칸이 벽인 경우
                # 반시계 방향으로 90도 회전
                else:
                    d = rotate(d)
            elif d == 1:
                if spaces[r][c+1] == 0:
                    c += 1
                    break
                else:
                    d = rotate(d)
            elif d == 2:
                if spaces[r+1][c] == 0:
                    r += 1
                    break
                else:
                    d = rotate(d)
            elif d == 3:
                if spaces[r][c-1] == 0:
                    c -= 1
                    break
                else:
                    d = rotate(d)
    # 상하좌우 4군데 중 1개도 빈 칸이 없으면
    else:
    	# 바라보는 방향을 유지한 채로 한 칸 후진
        if d == 0:
            r += 1
        elif d == 1:
            c -= 1
        elif d == 2:
            r -= 1
        else:
            c += 1

# 방 정보 값에서 청소된 자리(-1)의 개수를 출력
print(sum(row.count(-1) for row in spaces))

 

이상입니다.