출처 : https://www.acmicpc.net/problem/14503
14503번: 로봇 청소기
로봇 청소기가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오. 로봇 청소기가 있는 장소는 N×M 크기의 직사각형으로 나타낼 수 있으며, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 벽 또는 빈 칸이다. 청소기는 바라보는 방향이 있으며, 이 방향은 동, 서, 남, 북중 하나이다. 지도의 각 칸은 (r, c)로 나타낼 수 있고, r은 북쪽으로부터 떨어진 칸의 개수, c는 서쪽으로 부터 떨어진 칸의 개수이다. 로봇 청소기는 다음
www.acmicpc.net
In [1]:
N,M = map(int, input().split()) #N세로, M가로
# (r,c):칸의좌표
# d : 로봇 청소기가 바라보는 방향 / 0:북 1:동 2:남 3:서
r,c,d = map(int, input().split())
#로봇청소기가 청소해야할 방 / 1:벽, 0:청소가능 2:청소완료
room = []
for i in range(N):
room.append(list(map(int, input().split())))
'''
1.현재 위치를 청소한다.
2.현재 위치에서 현재 방향을 기준으로 왼쪽방향부터 차례대로 탐색을 진행한다.
2.1왼쪽 방향에 아직 청소하지 않은 공간이 존재한다면, 그 방향으로 회전한 다음 한 칸을 전진하고 1번부터 진행한다.
2.2왼쪽 방향에 청소할 공간이 없다면, 그 방향으로 회전하고 2번으로 돌아간다.
2.3네 방향 모두 청소가 이미 되어있거나 벽인 경우에는, 바라보는 방향을 유지한 채로 한 칸 후진을 하고 2번으로 돌아간다.
2.4네 방향 모두 청소가 이미 되어있거나 벽이면서, 뒤쪽 방향이 벽이라 후진도 할 수 없는 경우에는 작동을 멈춘다.
로봇 청소기는 이미 청소되어있는 칸을 또 청소하지 않으며, 벽을 통과할 수 없다.
'''
cnt = 0 ## cnt : 청소한 공간의 수
stop = 0
d_dictionary = {0:[0,-1], 1:[-1,0], 2:[0,1], 3:[1,0]} #현재 바라보고 있는 방향에 대해서 왼쪽을 바라볼때 r,c변화량
d_dictionary2 = {0:[-1,0], 1:[0,1], 2:[1,0], 3:[0,-1]} #현재 바라보고 있는 방향으로 한칸 전진할때 r,c 변화량
count = 2 ## 어떤 순서로 방이 청소되는지 보고싶어서 선언한 변수! 1부터 시작할 경우, 벽으로 인식할 수 있는 문제가 있다.
while(1):
#1.현재 위치를 청소한다
#여기를 if문으로 해줘야, 밑에 반복문에서 break를 걸어줬을때, 2번으로 돌아가는 것을 할 수 있다.
if(room[r][c]==0):
room[r][c] = count ## 임의의 숫자로 해줘도되지만, 어떤 순서로 청소되는지 보고 싶다. 2부터 시작!
count += 1
cnt += 1
#2. 현재 위치에서 현재 방향 기준, 왼쪽방향부터 차례대로 탐색
#2.1 왼쪽 방향에 청소가능 공간이 있다. 왼쪽으로 회전후, 한칸 전진, 1번부터 진행한다
new_r = r + d_dictionary[d][0]
new_c = c + d_dictionary[d][1]
if(0<=new_r and new_r<N and 0<=new_c and new_c<M and room[new_r][new_c]==0):
d = (d-1)%4
r = new_r
c = new_c
continue #아 여기서 continue를 해야 위로 올라가는구나
#2.2 왼쪽 방향에 청소가능 공간이 없다. 왼쪽으로 회전후, 2번으로 돌아간다.
for i in range(4):
new_r = r + d_dictionary[d][0]
new_c = c + d_dictionary[d][1]
if((0<=new_r and new_r<N and 0<=new_c and new_c<M and room[new_r][new_c]==0) is False):
d = (d-1)%4
#2.3 네 방향 모두 청소가 이미 되어있거나 벽인 경우에는, 바라보는 방향을 유지한 채로 한 칸 후진을 하고 2번으로 돌아간다.
if(i==3):
r = r - d_dictionary2[d][0]
c = c - d_dictionary2[d][1]
#2.4 후진했는데 벽일경우 -> 그럼 완전히 멈추면된다.
if(room[r][c]==1):
stop = 1
break
else:
continue # 이부분이 굳이 있어야 할까? 일단 작성해보고 나중에 판단// 없어도 될것 같다.
if(stop==1): ## 후진했는데 벽이어서 완전히 멈추는 경우 (while문을 벗어나야 한다.)
break
print(cnt)
In [2]:
## 2번 위치부터 순서대로 청소되는 위치를 보면 된다.
## 0:빈공간 1:벽
room
Out[2]:
'알고리즘 > [Python] 백준' 카테고리의 다른 글
| (Python) 백준 1018번 : 체스판 다시 칠하기 (0) | 2020.02.04 |
|---|---|
| (Python) 백준 2178번 : 미로 탐색 (0) | 2020.02.02 |
| (Python) 백준 1094번 : 막대기 (0) | 2020.01.22 |
| (Python) 백준 2455번 : 지능형 기차 (0) | 2020.01.15 |
| (Python) 백준 17779번 : 게리맨더링2 (0) | 2020.01.09 |