https://www.acmicpc.net/problem/23290
23290번: 마법사 상어와 복제
첫째 줄에 물고기의 수 M, 상어가 마법을 연습한 횟수 S가 주어진다. 둘째 줄부터 M개의 줄에는 물고기의 정보 fx, fy, d가 주어진다. (fx, fy)는 물고기의 위치를 의미하고, d는 방향을 의미한다. 방향
www.acmicpc.net
이 문제는 구현 문제로 문제에서 요구한 순서에 맞게 구현하는 것이 중요합니다.
주의할 점은 다음과 같습니다.
- 배열의 index가 0이 아닌 1번 부터 시작하도록 되어 있습니다. 물고기의 방향 정보 또한 1~8번 까지의 정보를 가지기 때문에 헷갈리지 않도록 조심해야합니다.
- 물고기의 냄새가 있는 곳은 '이동'을 못하는 것입니다. 따라서 물고기가 잡아 먹혀서 물고기 냄새가 생긴 경우에 기존의 물고기를 복제한다면 물고기의 냄새가 있어도 물고기가 존재할 수 있습니다.
- 상어의 이동, 상어는 3번 이동하는데, 기존에 이동했던 위치로도 이동할 수 있습니다.
ex) 상상하, 좌좌우, 좌우좌 - 물고기가 이동 못하는 경우, 문제에서 헷갈렸던 부분인데 물고기가 이동을 못하는 경우에 이동은 하지 않고 기존 위치의 물고기로 복제합니다.
풀이
1. 입력 및 변수 선언
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
|
from collections import defaultdict
M, S = map(int, input().split())
board = [[0] * 5 for _ in range(5)]
SHARK, SMELL = -1, 3
# ←, ↖, ↑, ↗, →, ↘, ↓, ↙
# 1 2 3 4 5 6 7 8
dy8 = ('NO USE', 0, -1, -1, -1, 0, 1, 1, 1)
dx8 = ('NO USE', -1, -1, 0, 1, 1, 1, 0, -1)
# ↑, ←, ↓, →
# 1 2 3 4
dy4 = ('NO USE', -1, 0, 1, 0)
dx4 = ('NO USE', 0, -1, 0, 1)
loc2fish= defaultdict(list) # 기존 물고기 저장 dict
moved_loc2fish = defaultdict(list) # 이동후의 물고기 dict
for i in range(M):
y, x, d = tuple(map(int, input().split()))
loc2fish[(y, x)].append(d)
shark_loc = tuple(map(int, input().split())) # 상어 위치
|
cs |
9~15번 라인 : 물고기는 8방향, 상어는 4방향으로 움직일 수 있기 때문에 이동 방향 배열을 2가지로 선언합니다.
17~18번 라인 : 물고기 정보를 저장한 dict 입니다. 물고기의 위치 (y, x)를 key, 해당 위치의 물고기들의 방향 정보 리스트를 value로 가집니다.
ex) loc2fish[(3, 2)] : 3행 2열에 위치한 물고기 들의 방향 정보
2. 물고기 이동
|
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
|
def move_fishes():
global moved_loc2fish
moved_loc2fish = defaultdict(list)
for loc, d_list in loc2fish.items():
y, x = loc
for d in d_list: # (y, x)에 저장된 물고기들의 이동 방향
can_go = False # 이동 가능 플래그
nd = d # nd를 바꿔가며 이동할 방향을 정함
for i in range(8):
ny = y + dy8[nd]
nx = x + dx8[nd]
if check_range(ny, nx) or board[ny][nx] > 0 or (ny, nx) == shark_loc:
# 이동이 불가능 한 경우 반시계 방향으로 nd 조정
nd = nd - 1 if nd != 1 else 8
continue
else:
# 이동이 가능한 경우
can_go = True # 이동 가능 플래그 기록
moved_loc2fish[(ny, nx)].append(nd) # 이동한 물고기 dict에 추가
break
if not can_go:
# 어느 방향으로도 이동할 수 없는 경우 현재 물고기 정보를 이동한 물고기 dict에 추가함
moved_loc2fish[loc].append(d)
|
cs |
7~22번 라인 : loc2fish에서 위치별로 물고기 방향 정보를 가져와 이동 가능한 위치를 조사합니다.
14번 라인 : 조사한 물고기 위치가 격자에서 벗어나는지 확인하고, 해당 위치에 물고기 냄새가 있는지, 상어 위치와 동일하지 않는지를 확인합니다.
16번 라인 : 이동이 불가능한 경우 반시계방향으로 방향을 조정합니다.
23번 라인 : 만약 물고기가 어느 방향으로도 이동할 수 없는 경우 현재 물고기 정보를 이동한 물고기 dict에 추가합니다.
3. 상어 이동
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
best_shark_move = None # 조건에 따라 가장 적합한 상어의 움직임 정보를 포함
def move_shark(shark, route, count, delete_loc):
if len(route) != 0:
if shark not in delete_loc: # 이미 방문한 상어 위치가 아닌 경우
count += len(moved_loc2fish[shark]) # 제외될 물고기 개수 추가
delete_loc.append(shark) # 제외된 위치 추가
if len(route) == 3: # 3번 움직인 경우
global best_shark_move
if best_shark_move == None: # best_shark_move가 None인 경우
best_shark_move = (int(route), count, shark, delete_loc) # (움직임 우선순위, 제외된 물고기 수, 상어의 마지막 위치, 제외된 위치 배열)
elif best_shark_move[1] < count or (best_shark_move[1] == count and best_shark_move[0] > int(route)):
# best_shark_move 보다 제외된 물고기 수가 더 많거나, 제외된 물고기 수는 같으나 움직임의 우선순위가 더 높은 경우
best_shark_move = (int(route), count, shark, delete_loc)
return
# 4방향으로 재귀함수를 호출하여 탐색
for i in range(1, 5, 1):
y, x = shark
ny = y + dy4[i]
nx = x + dx4[i]
if check_range(ny, nx):continue
else: move_shark((ny, nx), route+str(i), count, delete_loc.copy())
|
cs |
3번 라인 : route의 길이가 0인 경우는 첫 번째(시작 위치 이므로) 예외처리를 합니다.
4~6번 라인 : 이동한 shark의 위치가 이미 방문한 상어위치가 아닌 경우, 해당 위치에 존재하는 물고기의 개수를 count에 추가하고, 추후 해당 위치의 물고기 삭제를 위한 delete_loc 배열에 위치를 추가합니다.
8~15번 라인 : route의 길이가 3인 경우는 상어의 이동이 끝난 경우 입니다. 전역 변수 best_shark_move와 비교하여 더 우선순위가 높은 상어의 움직임을 best_shark_move 변수에 저장합니다. (저장하는 형태는 11번 라인 참조) 상어의 이동이 끝났으므로 함수를 종료합니다.
상어의 이동이 갱신되는 경우는 다음과 같습니다.
- 삭제된 물고기가 수가 더 많은 경우
- 삭제된 물고기가 수가 같고, 이동의 우선순위가 더 높은 경우( "333" < "111" )
18~23번 라인 : 재귀함수를 이용해서 상어를 4방향으로 이동합니다. 중복순열로 경우의 수는 4x4x4입니다. route 변수에는 상어의 이동 방향이 문자열로 저장됩니다. ex) "1", "11", "312"
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
|
def delete_and_update_fishes():
global loc2fish, moved_loc2fish, shark_move_result, shark_loc, best_shark_move
_, _, shark_next_loc, deleted_loc = best_shark_move # 가장 적합한 상어 움직임 정보를 가져옴
shark_loc = shark_next_loc # 상어 위치 갱신
# deleted_loc에 저장된 위치의 물고기들을 삭제하고, 냄새를 남김
for loc in deleted_loc:
y, x = loc
if moved_loc2fish[loc] != []:
board[y][x] = SMELL # 처음 SMELL = 3, 바로 다음 구문에서 냄새를 전부 1씩 없애기 때문
moved_loc2fish.pop(loc) # 이동한 물고기 정보에서 해당 위치 물고기 삭제
# 격자에 포함된 냄새 정부를 모두 -1씩함
for y in range(1, 5, 1):
for x in range(1, 5, 1):
if board[y][x] > 0:
board[y][x] -= 1
# 기존의 물고기 dict와 이동한 물고기 dict를 합침
for k, v in moved_loc2fish.items():
if v != []:
loc2fish[k].extend(v)
moved_loc2fish = defaultdict(list)
|
cs |
상어의 움직임에 따라 물고기 정보를 업데이트 합니다.
7~11번 라인 : 상어가 움직인 위치의 물고기들을 삭제하고, 냄새를 남깁니다. 처음 냄새의 값을 3으로 설정합니다.(다음 구문에서 냄새가 감소되기 때문)
14~17번 라인 : 격자에 저장된 냄새를 모두 1씩 감소시킵니다.
20~22번 라인 : 기존의 물고기 dict와 이동한 물고기 dict를 합칩니다.
전체 소스 코드
|
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
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
|
from collections import defaultdict
M, S = map(int, input().split())
board = [[0] * 5 for _ in range(5)]
SMELL = 3
# ←, ↖, ↑, ↗, →, ↘, ↓, ↙
# 1 2 3 4 5 6 7 8
dy8 = ('NO USE', 0, -1, -1, -1, 0, 1, 1, 1)
dx8 = ('NO USE', -1, -1, 0, 1, 1, 1, 0, -1)
# ↑, ←, ↓, →
# 1 2 3 4
dy4 = ('NO USE', -1, 0, 1, 0)
dx4 = ('NO USE', 0, -1, 0, 1)
loc2fish= defaultdict(list) # 기존 물고기 저장 dict
moved_loc2fish = defaultdict(list) # 이동후의 물고기 dict
for i in range(M):
y, x, d = tuple(map(int, input().split()))
loc2fish[(y, x)].append(d)
shark_loc = tuple(map(int, input().split())) # 상어 위치
def check_range(y, x):
return y < 1 or x < 1 or y > 4 or x > 4
def move_fishes():
global moved_loc2fish
moved_loc2fish = defaultdict(list)
for loc, d_list in loc2fish.items():
y, x = loc
for d in d_list: # (y, x)에 저장된 물고기들의 이동 방향
can_go = False # 이동 가능 플래그
nd = d # nd를 바꿔가며 이동할 방향을 정함
for i in range(8):
ny = y + dy8[nd]
nx = x + dx8[nd]
if check_range(ny, nx) or board[ny][nx] > 0 or (ny, nx) == shark_loc:
# 이동이 불가능 한 경우 반시계 방향으로 nd 조정
nd = nd - 1 if nd != 1 else 8
continue
else:
# 이동이 가능한 경우
can_go = True # 이동 가능 플래그 기록
moved_loc2fish[(ny, nx)].append(nd) # 이동한 물고기 dict에 추가
break
if not can_go:
# 어느 방향으로도 이동할 수 없는 경우 현재 물고기 정보를 이동한 물고기 dict에 추가함
moved_loc2fish[loc].append(d)
best_shark_move = None # 조건에 따라 가장 적합한 상어의 움직임 정보를 포함
def move_shark(shark, route, count, delete_loc):
if len(route) != 0:
if shark not in delete_loc: # 이미 방문한 상어 위치가 아닌 경우
count += len(moved_loc2fish[shark]) # 제외될 물고기 개수 추가
delete_loc.append(shark) # 제외된 위치 추가
if len(route) == 3: # 3번 움직인 경우
global best_shark_move
if best_shark_move == None: # best_shark_move가 None인 경우
best_shark_move = (int(route), count, shark, delete_loc) # (움직임 우선순위, 제외된 물고기 수, 상어의 마지막 위치, 제외된 위치 배열)
elif best_shark_move[1] < count or (best_shark_move[1] == count and best_shark_move[0] > int(route)):
# best_shark_move 보다 제외된 물고기 수가 더 많거나, 제외된 물고기 수는 같으나 움직임의 우선순위가 더 높은 경우
best_shark_move = (int(route), count, shark, delete_loc)
return
# 4방향으로 재귀함수를 호출하여 탐색
for i in range(1, 5, 1):
y, x = shark
ny = y + dy4[i]
nx = x + dx4[i]
if check_range(ny, nx):continue
else: move_shark((ny, nx), route+str(i), count, delete_loc.copy())
def delete_and_update_fishes():
global loc2fish, moved_loc2fish, shark_move_result, shark_loc, best_shark_move
_, _, shark_next_loc, deleted_loc = best_shark_move # 가장 적합한 상어 움직임 정보를 가져옴
shark_loc = shark_next_loc # 상어 위치 갱신
# deleted_loc에 저장된 위치의 물고기들을 삭제하고, 냄새를 남김
for loc in deleted_loc:
y, x = loc
if moved_loc2fish[loc] != []:
board[y][x] = SMELL # 처음 SMELL = 3, 바로 다음 구문에서 냄새를 전부 1씩 없애기 때문
moved_loc2fish.pop(loc) # 이동한 물고기 정보에서 해당 위치 물고기 삭제
# 격자에 포함된 냄새 정부를 모두 -1씩함
for y in range(1, 5, 1):
for x in range(1, 5, 1):
if board[y][x] > 0:
board[y][x] -= 1
# 기존의 물고기 dict와 이동한 물고기 dict를 합침
for k, v in moved_loc2fish.items():
if v != []:
loc2fish[k].extend(v)
moved_loc2fish = defaultdict(list)
def simulation():
# 1. 물고기 이동
move_fishes()
# 2. 상어 이동
global best_shark_move
best_shark_move = None
move_shark(shark_loc, "", 0, [])
# 3. 상어 이동에 따라 물고기 갱신
delete_and_update_fishes()
for i in range(S):
simulation()
# 남아있는 물고기 개수 출력
result = 0
for k, v in loc2fish.items():
result += len(v)
print(result)
|
cs |
'About > Algorithm' 카테고리의 다른 글
| [백준 21610] 마법사 상어와 비바라기(Python 풀이) (0) | 2022.02.24 |
|---|---|
| [백준 23288] 주사위 굴리기 2 (Python 풀이) (0) | 2022.02.22 |
| [Programmers] 표 편집(Python 풀이) - 2021 카카오 채용연계형 인턴십 코딩 테스트 문제 (0) | 2022.02.09 |
| [Programmers] 파괴되지 않은 건물 (Python 풀이) - 2022 KAKAO BLIND RECRUITMENT (9) | 2022.02.03 |
| [Programmers] 양과 늑대 (Python 풀이) - 2022 KAKAO BLIND RECRUITMENT (0) | 2022.01.28 |
