14503번: 로봇 청소기
로봇 청소기가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오. 로봇 청소기가 있는 장소는 N×M 크기의 직사각형으로 나타낼 수 있으며, 1×1크기의 정사각형 칸으로 나누어
www.acmicpc.net
문제 해결을 위한 과정
이 문제의 경우 전형적인 구현 알고리즘입니다. 문제의 조건을 잘 따라가기만 한다면 그다지 큰 어려움 없이 해결할 수 있는 문제입니다. 먼저 문제에서 그래프의 정보와 시작 지점을 입력받습니다. 그 후 방향을 좌측으로 돌린 후 해당 지역이 청소가 필요한 지역이면 청소를 하고 지점을 옮겨줍니다. 벽인 경우는 방향을 다시 좌측으로 돌려줍니다. 이렇게 4번 돌리게 되면 해당 지역 주변에는 청소할 수 있는 지점이 없기 때문에 방향을 유지한 채로 뒤로 후진합니다. 이것은
nx = x - dx[direction], ny = y - dy[direction]으로 구현합니다.
만약 4방향 모두 청소할 수 없는 칸이여서 후진해야 하는데 후진해야 할 칸이 벽이어서 후진할 수 없는 경우 종료하고 청소했던 칸의 숫자를 출력합니다.(소스코드에 주석을 첨부합니다.)
소스코드
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
|
n, m = map(int, input().split())
r, c, d = map(int, input().split())
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]
graph = []
for i in range(n):
graph.append(list(map(int, input().split())))
def turn_left(): # 방향을 좌측으로 돌리는 함수 0인경우 3이 나온다. 1인 경우는 0이 나온다. 나머지도 마찬가지
global d
d = (d-1) % 4
count = 1
x, y = r, c
graph[x][y] = 2 # 방문처리를 2로 함
while True:
check = False # 방문한 칸이 있는지 없는지 유뮤를 판단하기 위한 bool형 변수 check
for i in range(4): # 4방향을 돌며
turn_left()
nx = x + dx[d]
ny = y + dy[d]
if 0 <= nx < n and 0 <= ny < m: # nx, ny가 그래프를 벗어나지 않는지 확인
if graph[nx][ny] == 0: # 청소할 수 있는 칸인 경우
count += 1
graph[nx][ny] = 2 # 방문처리 해줌
x, y = nx, ny
check = True # check를 True로 바꾸어 주어 방문했음을 알림
break
if not check: # 4방향을 확인했음에도 청소할 공간이 없는 경우 후진
nx = x - dx[d]
ny = y - dy[d]
if 0 <= nx < n and 0 <= ny < m: # nx, ny가 그래프를 벗어나지 않는지 확인
if graph[nx][ny] == 2: # 2라면 즉 이미 청소한 칸인경우 후진
x, y = nx, ny
elif graph[nx][ny] == 1: # 1인경우 즉 벽인 경우
print(count)
break
else:
print(count)
break
|
cs |
'알고리즘 > 백준' 카테고리의 다른 글
| 백준 알고리즘 11724: 연결 요소의 개수(Python) (0) | 2021.02.05 |
|---|---|
| 백준 알고리즘 1012: 유기농 배추(Python) (0) | 2021.02.05 |
| 백준 알고리즘 10773: 제로(Python) (0) | 2021.02.03 |
| 백준 알고리즘 1475: 방 번호(Python) (0) | 2021.02.03 |
| 백준 알고리즘 7568: 덩치(Python) (0) | 2021.02.03 |