https://www.acmicpc.net/problem/20055
20055번: 컨베이어 벨트 위의 로봇
길이가 N인 컨베이어 벨트가 있고, 길이가 2N인 벨트가 이 컨베이어 벨트를 위아래로 감싸며 돌고 있다. 벨트는 길이 1 간격으로 2N개의 칸으로 나뉘어져 있으며, 각 칸에는 아래 그림과 같이 1부
www.acmicpc.net
해당 문제는 골드5 레벨의 구현 문제입니다.
풀이
0. 전역 변수 및 입력
|
1
2
3
4
5
6
7
8
|
from copy import deepcopy
N, K = map(int, input().split())
robots = []
belts = list(map(int, input().split())) # 컨베이어 벨트 - 1차원 리스트로 표현(2*N개)
belts.insert(0, -1) # dummy
is_robot = [False for _ in range(len(belts))] # 컨베이어 벨트의 index 위치에 로봇이 있는지 확인하기 위함
|
cs |
위와 같이 입력 및 전역 변수를 초기화합니다.
- 그림에서는 컨베이어 벨트가 나누어져있지만, 해당 풀이에서는 1차원 리스트로 표현하였습니다. 0번째에 더미값을 추가하여 1~2N까지의 index를 가지게 하였습니다.
- robots[] 는 로봇들의 위치를 나타내는 배열입니다.
- is_robot[] 은 해당 컨베이어 벨트의 index에 로봇이 있는지 없는지를 알려주는 리스트입니다.
1. 컨베이어 및 로봇 회전
벨트가 각 칸 위에 있는 로봇과 함께 한 칸 회전합니다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
def rotate():
# 컨베이어 벨트 및 벨트 위 로봇 회전
global belts, is_robot, robots
# 벨트 회전
n = belts.pop()
belts.insert(1, n)
# 로봇 회전
new_robot = [] # 회전 후 로봇 저장
is_robot = [False for _ in range(len(belts))] # 로봇 존재 여부 초기화
for belt_index in robots:
next_belt_index = belt_index + 1 # 다음 칸으로 이동
if next_belt_index < N: # 다음 칸이 N이하인 경우 새 로봇 배열에 추가 -> 다음 칸이 N인 경우 제외(내린것으로 판단)
new_robot.append(next_belt_index)
is_robot[next_belt_index] = True
robots = deepcopy(new_robot) # 기존 로봇 배열과 교환
|
cs |
- 컨베이어 벨트는 1차원 리스트로 구성하였으므로 리스트의 가장 마지막 원소를 가져와서 리스트의 가장 첫번째에 삽입합니다.(원형 큐와 비슷한 형태)
- 컨베이어 위의 로봇을 회전시킬 때는 robots 배열에서 로봇의 위치 정보(belts[]에서의 Index)를 가져와서 +1씩해줍니다.
만약 index의 값이 N이 되는 경우 '내리는 위치'에 도착한 것이므로 회전 후의 로봇 배열에 포함하지 않습니다.
- 이동 후의 로봇의 존재 여부를 is_robot[]에 기록합니다.
2. 로봇 이동
가장 먼저 벨트에 올라간 로봇부터, 벨트가 회전하는 방향으로 한 칸 이동할 수 있다면 이동한다. 만약 이동할 수 없다면 가만히 있는다.
로봇이 이동하기 위해서는 이동하려는 칸에 로봇이 없으며, 그 칸의 내구도가 1 이상 남아 있어야 한다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
def move_robots():
# 로봇 이동
global is_robot, robots, belts
new_robots = [] # 새로운 로봇 배열
for belt_index in robots:
next_index = belt_index + 1 # 다음 로봇 위치
if is_robot[next_index] or belts[next_index] < 1: # 이동이 불가능한 경우(로봇이 있거나 내구도 1미만)
new_robots.append(belt_index)
else: # 이동이 가능한 경우
belts[next_index] -= 1 # 다음 위치의 벨트 내구도 1 감소
is_robot[belt_index] = False # 현재 위치에 로봇이 존재하지 않게됨
if next_index != N: # 다음 위치가 N이 아닌경우에만(중요)
new_robots.append(next_index) # 새로운 로봇 배열에 추가
is_robot[next_index] = True
robots = deepcopy(new_robots)
|
cs |
- robots[] 배열에서 로봇의 위치(betls의 index)를 가져와 다음 위치를 조사합니다(코드에서 next_index)
- 다음 위치에 로봇이 있거나, 벨트의 내구도가 1 미만인 경우 로봇이 이동하지 않으므로, 이동 후 로봇 배열(new_robots)에 기존의 위치 정보를 삽입합니다. (7~8번 라인)
- 이동이 가능한 경우 다음 위치의 벨트 내구도를 1 감소시킵니다. 그리고 is_robot에 현재 위치의 로봇은 없는 것으로 표기합니다,
- 이동이 가능하며 다음 위치가 N이 아닌 경우에만 이동 후의 로봇 배열에 다음 위치 정보를 삽입하며 is_robot에 로봇 존재 여부를 기록합니다. (12~14번 라인)
3. 로봇 삽입
올리는 위치에 있는 칸의 내구도가 0이 아니면 올리는 위치에 로봇을 올린다.
|
1
2
3
4
5
6
7
|
def insert_robot():
global is_robot, robots
if belts[1] != 0: # 1번째 벨트의 내구도가 0이 아닌경우
robots.append(1) # 새로운 로봇 위치(1번째) 추가
# 내구도 감소 및 로봇 존재 여부 기록
belts[1] -= 1
is_robot[1] = True
|
cs |
- belts[] 배열의 1번째 벨트의 내구도가 0이 아닌 경우 robots[] 배열에 새로운 로봇을 추가합니다.
- 배열의 마지막에 로봇의 인덱스를 하도록 구현하였기 때문에 2. 로봇 이동에서 '가장 먼저 벨트에 올라간 로봇' 부터 계산하게 됩니다.
4. 종료 조건 확인
내구도가 0인 칸의 개수가 K개 이상이라면 과정을 종료한다. 그렇지 않다면 1번으로 돌아간다.
|
1
2
3
4
|
def is_finish():
# 0의 개수가 K개 이상이 경우 True 아닌 경우 False 반환
return belts.count(0) >= K
|
cs |
전체 흐름
전체 함수를 다음과 같이 실행합니다.
|
1
2
3
4
5
6
7
8
9
10
11
|
cnt = 0
while not is_finish(): # is_finish() 함수가 True를 반환할 때 까지 반복
cnt += 1
# 1. 컨베이어 및 로봇 회전
rotate()
# 2. 로봇 이동
move_robots()
# 3. 로봇 삽입
insert_robot()
print(cnt)
|
cs |
전체 소스 코드
|
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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
|
from copy import deepcopy
N, K = map(int, input().split())
robots = []
belts = list(map(int, input().split())) # 컨베이어 벨트 - 1차원 리스트로 표현(2*N개)
belts.insert(0, -1) # dummy
is_robot = [False for _ in range(len(belts))] # 컨베이어 벨트의 index 위치에 로봇이 있는지 확인하기 위함
def rotate():
# 컨베이어 벨트 및 벨트 위 로봇 회전
global belts, is_robot, robots
# 벨트 회전
n = belts.pop()
belts.insert(1, n)
# 로봇 회전
new_robot = [] # 회전 후 로봇 저장
is_robot = [False for _ in range(len(belts))] # 로봇 존재 여부 초기화
for belt_index in robots:
next_belt_index = belt_index + 1 # 다음 칸으로 이동
if next_belt_index < N: # 다음 칸이 N이하인 경우 새 로봇 배열에 추가 -> 다음 칸이 N인 경우 제외(내린것으로 판단)
new_robot.append(next_belt_index)
is_robot[next_belt_index] = True
robots = deepcopy(new_robot) # 기존 로봇 배열과 교환
def move_robots():
# 로봇 이동
global is_robot, robots, belts
new_robots = [] # 새로운 로봇 배열
for belt_index in robots:
next_index = belt_index + 1 # 다음 로봇 위치
if is_robot[next_index] or belts[next_index] < 1: # 이동이 불가능한 경우(로봇이 있거나 내구도 1미만)
new_robots.append(belt_index)
else: # 이동이 가능한 경우
belts[next_index] -= 1 # 다음 위치의 벨트 내구도 1 감소
is_robot[belt_index] = False # 현재 위치에 로봇이 존재하지 않게됨
if next_index != N: # 다음 위치가 N이 아닌경우에만(중요)
new_robots.append(next_index) # 새로운 로봇 배열에 추가
is_robot[next_index] = True
robots = deepcopy(new_robots)
def insert_robot():
global is_robot, robots
if belts[1] != 0: # 1번째 벨트의 내구도가 0이 아닌경우
robots.append(1) # 새로운 로봇 위치(1번째) 추가
# 내구도 감소 및 로봇 존재 여부 기록
belts[1] -= 1
is_robot[1] = True
def is_finish():
# 0의 개수가 K개 이상이 경우 True 아닌 경우 False 반환
return belts.count(0) >= K
cnt = 0
while not is_finish(): # is_finish() 함수가 True를 반환할 때 까지 반복
cnt += 1
# 1. 컨베이어 및 로봇 회전
rotate()
# 2. 로봇 이동
move_robots()
# 3. 로봇 삽입
insert_robot()
print(cnt)
|
cs |
'About > Algorithm' 카테고리의 다른 글
| [Algorithm] 삼성 SW 역량 테스트(코딩 테스트) 자주 나오는 알고리즘 유형 정리(유형별 Python Code 및 문제) (2) | 2022.04.05 |
|---|---|
| [백준 20056] 마법사 상어와 파이어볼(Python 풀이) (0) | 2022.03.29 |
| [백준 21609] 상어중학교 (C++ 풀이) (0) | 2022.03.28 |
| [백준 21611번] 마법사 상어와 블리자드(Python 풀이) (0) | 2022.02.25 |
| [백준 21610] 마법사 상어와 비바라기(Python 풀이) (0) | 2022.02.24 |
