https://www.acmicpc.net/problem/21611
21611번: 마법사 상어와 블리자드
마법사 상어는 파이어볼, 토네이도, 파이어스톰, 물복사버그, 비바라기 마법을 할 수 있다. 오늘 새로 배운 마법은 블리자드이고, 크기가 N×N인 격자에서 연습하려고 한다. N은 항상 홀수이고, (
www.acmicpc.net
이 문제는 골드1 난이도의 '구현' 문제입니다.
풀이
복잡한 과정을 좀 더 쉽게 풀이하기 위하여 2차원 격자를 1차원으로 변환하여 풀이하였으며, 절차가 많고 복잡하므로 단계를 함수단위로 나누어 풀이하였습니다. 풀이 순서는 다음과 같습니다.
1. 격자 초기화(2차원 -> 1차원)
2. 방향과 거리를 기준으로 구슬 파괴
3. 파괴된 구슬 정리
4. 연속하는 구슬 파괴 및 정리
5. 구슬 변화
전체 소스코드는 마지막에 있습니다.
1. 격자 초기화
격자는 나선형의 규칙을 가지면서 번호를 매깁니다.
여기서 '나선형의 규칙'이란 다음과 같습니다. 기본 이동 거리 dist = 1, dir = 서쪽이라고 생각하자.
- dir 방향으로 dist 만큼 이동한다. (시작 좌표를 기준)
- dir를 회전한다.
- 회전한 dir 방향으로 dist만큼 이동한다.
- dir를 회전하고, dist에 1을 추가한다.
즉, 두 번 방향을 바꿀 때 마다 한 방향으로 이동하는 거리를 1 증가시키도록 번호를 매깁니다. 이를 이용하여 2차원 격자를 1차원으로 변환하는 함수 init_grid()는 다음과 같습니다.(위의그림에서는 중간 좌표(N/2, N/2)에서 부터 시작했지만, 코드에서는 마지막(0, 0)에서 부터 번호를 매기도록 구현하였음.)
|
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
|
N, M = map(int, input().split())
board = [list(map(int, input().split())) for _ in range(N)]
magics = [tuple(map(int, input().split())) for _ in range(M)]
n2loc = {} # 번호 -> 좌표
loc2n = {} # 좌표 -> 번호
n2ball = [-1] * N**2 # 번호 -> 번호에 해당하는 공 번호
result = 0
def init_grid():
"""
2차원 좌표 정보를 1차원으로 변경
:return:
"""
global n2loc, loc2n
# 우 하 좌 상
dy_temp = (0, 1, 0, -1)
dx_temp = (1, 0, -1, 0)
loc = (0, -1) # 시작을 (0, -1)로 해서 (0, 0)에서 부터 시작하도록
cnt = N ** 2 - 1 # 마지막 번호 = N^2-1
dist, dist_change_flag = N, 1 # 처음 이동거리 N, 이동거리 변화 Flag
dir = 0
while True:
for i in range(dist):
ny = loc[0] + dy_temp[dir]
nx = loc[1] + dx_temp[dir]
loc = (ny, nx) # 좌표 갱신
n2loc[cnt] = (ny, nx) # 번호 -> 좌표
loc2n[(ny, nx)] = cnt # 좌표 -> 번호
n2ball[cnt] = board[ny][nx] # 번호 -> 구슬 번호
cnt -= 1
dir = (dir + 1) % 4 # 방향 번경
dist_change_flag += 1
if dist_change_flag == 2: # 방향을 2번 변경하면 dist 1 감소
dist_change_flag = 0
dist -= 1
if dist == 0: break # 거리가 0이 되면 종료
|
cs |
- n2loc, loc2n 은 좌표<->번호를 얻는 Dictionary 입니다.
- n2ball은 격자 번호를 index로 하여 구슬의 숫자를 저장하는 List입니다>
- 27~44번 줄에서 '나선형의 규칙'을 이용하여 2차원 격자 -> 1차원 리스트로 변환합니다.
2. 구슬 파괴
구현에 필요한 모든 내용은 1. 격자 초기화 단계에서 모두 마쳤습니다. 이를 이용하여 먼저 방향과 거리를 기준으로 구슬을 파괴합니다. 이에 해당하는 함수 destroy(d, s)는 다음과 같습니다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
def destroy(d, s):
"""
방향과 거리에 따라서 구슬들을 파괴함
:param d: 방향
:param s: 거리
:return:
"""
# 상하좌우
dy = ("", -1, 1, 0, 0)
dx = ("", 0, 0, -1, 1)
shark_loc = (int(N / 2), int(N / 2)) # 상어 좌표
y, x = shark_loc
# 거리 상에 존재하는 구슬 모두 파괴
for i in range(1, s+1, 1):
ny = y + dy[d] * i
nx = x + dx[d] * i
n = loc2n[(ny, nx)] # 좌표 -> 번호를 얻음
n2ball[n] = -1 # 해당 번호의 구슬 값을 -1(빈칸)으로 변경
|
cs |
- 상어의 좌표를 이용하여 방향 d의 s거리 이내에 놓인 구슬을 모두 파괴합니다.
- loc2n을 이용하여 좌표에 해당하는 번호를 얻고, n2ball의 해당 번호를 -1로 만들어 파괴되었다는 것을 표시합니다.
그림으로 표현하면 다음과 같습니다.
3. 파괴된 구슬 정리
파괴된 구슬을 정리하는 함수 arrangement()는 다음과 같습니다.
|
1
2
3
4
5
6
7
8
9
|
def arrangement():
"""
파괴된 구슬을 정리 (빈 칸에 구슬들을 채움)
:return:
"""
global n2ball
del_cnt = n2ball.count(-1)
n2ball = [ball for ball in n2ball if ball != -1] # -1(빈 칸)을 제외하고 다시 n2ball 배열 생성
n2ball.extend([0]*del_cnt) # 제외된 칸이 있기 때문에 그만큼 다시 배열을 채워줌
|
cs |
- 빈 칸들을 모두 앞당겨 채우면 되는데, 2차원 배열이었다면, 복잡했겠지만 1차원 배열(n2ball)으로 변환하였기에 -1을 제외하여 다시 배열을 생성하면 모든 칸이 앞당겨진것 처럼 됩니다.
- 제외된 칸이 있기 때문에 새로운 배열은 개수가 맞지 않습니다. 따라서 제외된 개수 만큼 배열의 마지막에 0을 추가합니다.
또한 이 함수는 4. 연속하는 구슬 삭제 단계에서도 재활용하는 함수입니다.
4. 연속하는 구슬 삭제
연속하는 구슬을 삭제하는 함수 destroy2()는 다음과 같습니다.
|
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
|
def destroy2():
"""
연속하는 구슬 삭제
:return: 구슬 삭제 여부(True or False)
"""
global result
ret = False # 구슬이 하나도 파괴되지 않은 경우 False 반환
cnt = 0
target = 0 # 같은 구슬인지 비교할 대상의 번호
ball_num = 0 # 해당 번호의 구슬의 숫자
for i in range(N**2): # 0~N^2-1번 까지 연속하는 구슬인지 조사
if n2ball[i] == n2ball[target]: # 연속하는 경우
cnt += 1 # count += 1
else:
# 연속하지 않는 경우
if cnt >= 4: # 4개 이상 연속한다면
ret = True
for n in range(target, i, 1): # 해당 번호의 구슬 삭제
n2ball[n] = -1
result += ball_num * cnt # 점수 추가
# count, 비교 대상, 번호의 구슬 숫자 초기화
cnt = 1
target = i
ball_num = n2ball[i]
return ret # True or False 반환
|
cs |
- 0~N^2-1까지 연속하는 구슬인지 조사하여 연속하는 구슬을 삭제합니다. 구슬이 삭제되는 경우 구슬의 번호x개수를 글로벌 변수 result에 추가합니다.
- 구슬을 삭제한 후 다시 연속하는 구슬이 생기면 다시 삭제해줘야 하기 때문에 destroy2() 함수가 True를 반환하면 구슬이 삭제되었다는 것을, False를 반환하면 구슬이 삭제되지 않았다는 것을 의미합니다.
따라서 destroy2() 함수는 구슬이 삭제되지 않을 때 까지 destroy2() -> arrangement() -> destroy2() -> ... 를 반복합니다.
|
1
2
3
|
while True:
if not destroy2(): break
arrangement()
|
cs |
5. 구슬 변화
구슬을 모두 파괴한 후 구슬이 변화합니다. 이에 해당하는 함수 translate_all_balls()는 다음과 같습니다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
def translate_all_balls():
"""
구슬 변화, 연속하는 구슬을 '구슬 개수', '구슬 번호'로 변환하여 n2ball에 추가함
"""
global n2ball
new_n2ball = [0] # 새로운 n2ball, 첫 인덱스에 상어를 의미하는 공백 추가
group = [] # 연속하는 구슬 저장용 배열
for n in range(1, N**2, 1):
if not group: group.append(n2ball[n]) # group이 []이면 n번째의 구슬 추가
elif n2ball[n] == group[0]: # group에 들어있는 구슬 번호가 같은경우
group.append(n2ball[n]) # 현재 구슬 추가
else:
# group에 들어있는 구슬이 다른 경우(연속된 구슬의 종료 시점)
new_n2ball.append(len(group)) # 구슬의 개수
new_n2ball.append(group[0]) # 구슬의 번호를 차례대로 추가
group = [n2ball[n]] # group을 원소를 현재 구슬로 초기화(뒷 loop 부터는 현재 원소를 기준으로 탐색)
n2ball = [0] * N ** 2 # n2ball 초기화 후 new_n2ball을 복사함
for i in range(len(new_n2ball)):
if i >= (N ** 2): break # 번호가 넘어가는 경우 break
n2ball[i] = new_n2ball[i]
|
cs |
- 아까와 비슷하게 연속하는 구슬을 조사하고, 이를 '연속한 구슬 개수', '구슬 번호'로 변환하여 new_n2ball에 추가합니다.
- 18~21번 라인에서 new_n2ball을 n2ball에 복사합니다.
전체 함수 흐름
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
def solve():
# 1. 격자 초기화
init_grid()
for d, s in magics:
# 2. 방향과 거리를 기준으로 구슬 파괴
destroy(d, s)
# 3. 파괴된 구슬 정리
arrangement()
# 4. 연속하는 구슬 파괴 및 정리
while True:
if not destroy2(): break
arrangement()
# 5. 구슬 변화
translate_all_balls()
# print_ball()
solve()
print(result)
|
cs |
1~5번의 함수를 정리하면 위와 같습니다.
전체 소스코드
|
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
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
|
N, M = map(int, input().split())
board = [list(map(int, input().split())) for _ in range(N)]
magics = [tuple(map(int, input().split())) for _ in range(M)]
n2loc = {} # 번호 -> 좌표
loc2n = {} # 좌표 -> 번호
n2ball = [-1] * N**2 # 번호 -> 번호에 해당하는 공 번호
result = 0
def print_ball(): # 디버그
for i in range(N):
print([n2ball[loc2n[(i, j)]] for j in range(N)])
print()
def init_grid():
"""
2차원 좌표 정보를 1차원으로 변경
:return:
"""
global n2loc, loc2n
# 우 하 좌 상
dy_temp = (0, 1, 0, -1)
dx_temp = (1, 0, -1, 0)
loc = (0, -1) # 시작을 (0, -1)로 해서 (0, 0)에서 부터 시작하도록
cnt = N ** 2 - 1 # 마지막 번호 = N^2-1
dist, dist_change_flag = N, 1 # 처음 이동거리 N, 이동거리 변화 Flag
dir = 0
while True:
for i in range(dist):
ny = loc[0] + dy_temp[dir]
nx = loc[1] + dx_temp[dir]
loc = (ny, nx) # 좌표 갱신
n2loc[cnt] = (ny, nx) # 번호 -> 좌표
loc2n[(ny, nx)] = cnt # 좌표 -> 번호
n2ball[cnt] = board[ny][nx] # 번호 -> 구슬 번호
cnt -= 1
dir = (dir + 1) % 4 # 방향 번경
dist_change_flag += 1
if dist_change_flag == 2: # 방향을 2번 변경하면 dist 1 감소
dist_change_flag = 0
dist -= 1
if dist == 0: break # 거리가 0이 되면 종료
def arrangement():
"""
파괴된 구슬을 정리 (빈 칸에 구슬들을 채움)
:return:
"""
global n2ball
del_cnt = n2ball.count(-1)
n2ball = [ball for ball in n2ball if ball != -1] # -1(빈 칸)을 제외하고 다시 n2ball 배열 생성
n2ball.extend([0]*del_cnt) # 제외된 칸이 있기 때문에 그만큼 다시 배열을 채워줌
def destroy(d, s):
"""
방향과 거리에 따라서 구슬들을 파괴함
:param d: 방향
:param s: 거리
:return:
"""
# 상하좌우
dy = ("", -1, 1, 0, 0)
dx = ("", 0, 0, -1, 1)
shark_loc = (int(N / 2), int(N / 2)) # 상어 좌표
y, x = shark_loc
# 거리 상에 존재하는 구슬 모두 파괴
for i in range(1, s+1, 1):
ny = y + dy[d] * i
nx = x + dx[d] * i
n = loc2n[(ny, nx)] # 좌표 -> 번호를 얻음
n2ball[n] = -1 # 해당 번호의 구슬 값을 -1(빈칸)으로 변경
def destroy2():
"""
연속하는 구슬 삭제
:return: 구슬 삭제 여부(True or False)
"""
global result
ret = False # 구슬이 하나도 파괴되지 않은 경우 False 반환
cnt = 0
target = 0 # 같은 구슬인지 비교할 대상의 번호
ball_num = 0 # 해당 번호의 구슬의 숫자
for i in range(N**2): # 0~N^2-1번 까지 연속하는 구슬인지 조사
if n2ball[i] == n2ball[target]: # 연속하는 경우
cnt += 1 # count += 1
else:
# 연속하지 않는 경우
if cnt >= 4: # 4개 이상 연속한다면
ret = True
for n in range(target, i, 1): # 해당 번호의 구슬 삭제
n2ball[n] = -1
result += ball_num * cnt # 점수 추가
# count, 비교 대상, 번호의 구슬 숫자 초기화
cnt = 1
target = i
ball_num = n2ball[i]
return ret # True or False 반환
def translate_all_balls():
"""
구슬 변화, 연속하는 구슬을 '구슬 개수', '구슬 번호'로 변환하여 n2ball에 추가함
"""
global n2ball
new_n2ball = [0] # 새로운 n2ball, 첫 인덱스에 상어를 의미하는 공백 추가
group = [] # 연속하는 구슬 저장용 배열
for n in range(1, N**2, 1):
if not group: group.append(n2ball[n]) # group이 []이면 n번째의 구슬 추가
elif n2ball[n] == group[0]: # group에 들어있는 구슬 번호가 같은경우
group.append(n2ball[n]) # 현재 구슬 추가
else:
# group에 들어있는 구슬이 다른 경우(연속된 구슬의 종료 시점)
new_n2ball.append(len(group)) # 구슬의 개수
new_n2ball.append(group[0]) # 구슬의 번호를 차례대로 추가
group = [n2ball[n]] # group을 원소를 현재 구슬로 초기화(뒷 loop 부터는 현재 원소를 기준으로 탐색)
n2ball = [0] * N ** 2 # n2ball 초기화 후 new_n2ball을 복사함
for i in range(len(new_n2ball)):
if i >= (N ** 2): break # 번호가 넘어가는 경우 break
n2ball[i] = new_n2ball[i]
def solve():
# 1. 격자 초기화
init_grid()
for d, s in magics:
# 2. 방향과 거리를 기준으로 구슬 파괴
destroy(d, s)
# 3. 파괴된 구슬 정리
arrangement()
# 4. 연속하는 구슬 파괴 및 정리
while True:
if not destroy2(): break
arrangement()
# 5. 구슬 변화
translate_all_balls()
# print_ball()
solve()
print(result)
|
cs |
감사합니다.
'About > Algorithm' 카테고리의 다른 글
| [백준 20055] 컨베이어 벨트 위의 로봇(Python 풀이) (0) | 2022.03.29 |
|---|---|
| [백준 21609] 상어중학교 (C++ 풀이) (0) | 2022.03.28 |
| [백준 21610] 마법사 상어와 비바라기(Python 풀이) (0) | 2022.02.24 |
| [백준 23288] 주사위 굴리기 2 (Python 풀이) (0) | 2022.02.22 |
| [백준 23290] 마법사 상어와 복제(Python 풀이) (0) | 2022.02.14 |
