A:1, C:2, G:3, T:4 이며 'A,C,G,T'로 이루어진 문자열 S를 P[i]부터 Q[i]까지 범위의 인덱스로 잘랐을 때
해당 문자열 내의 최솟값을 구하는 문제이다.
즉, 'CAGCCTA' 라는 문자열 S가 주어지고, P[0] = 2, Q[0] = 4 이면
자른 문자열은 GCC가 되고 여기서 최솟값은 C = 2가 된다.
풀이 과정
이 문제를 풀면서 굉장히 의아한 부분이 있다.
먼저, 문제의 의도는 Prefix Sum을 이용하는 문제이지만, 파이썬으로 풀었을 때 굉장히 간단한 방법으로 다음과 같이 풀어보았다.
[파이썬 코드]
def solution(S, P, Q):
arr = []
for i in range(len(P)):
A = P[i]
B = Q[i]
tmp = S[A:B+1]
if 'A' in tmp:
arr.append(1)
elif 'C' in tmp:
arr.append(2)
elif 'G' in tmp:
arr.append(3)
else:
arr.append(4)
return arr
현재 지점에서 다음 지점(아래 지점)으로 이동할 때는, 왼쪽대각선과 오른쪽 대각선으로만 갈 수 있다.
이 방법으로 탐색했을 때, 탐색경로에 있는 숫자들을 모두 더했을 때의 최대가 되는 경로를 구하는 문제이다.
풀이 과정
이 문제는DP(다이나믹 프로그래밍)을 이용해 앞에서부터 최댓값을 저장해나가며 푸는 문제이다.
가장 첫번째 열에 있는 숫자(7, 3, 8, 2, 4)들은 선택의 여지 없이 이전의 가장 왼쪽 수를 선택해야 한다.
예를 들어, 3번째 줄의 가장 왼쪽 숫자인 8은 2번째 줄의 3을 선택했을 때의 경로를 따라야 하며
4번째 줄의 가장 왼쪽 숫자인 2는 3번째 줄의 8을 선택했을 때의 경로를 따라야 한다.
그 이외의 숫자들은 이전(위) 숫자 두개 중 최댓값을 선택할 수 있다.
이러한 특징을 반영하여 DP배열을 2차원으로 만들어 아래와 같은 코드를 짤 수 있다.
DP[1][0]에는 1번째 줄의 0번째 수를 선택했을 때의 최댓값을 저장하고
DP[1][1]에는 1번째 줄의 1번째 수를 선택했을 때의 최댓값을 저장한다.
이를 파이썬 코드로 나타내면 다음과 같다.
n = int(input())
arr = []
dp = [[0]*n for _ in range(n)]
for i in range(n):
arr.append(list(map(int, input().split())))
dp[0][0] = arr[0][0]
for i in range(1, n):
for j in range(0, i+1):
if j == 0:
dp[i][j] = dp[i-1][j] + arr[i][j]
else:
dp[i][j] = max(dp[i-1][j-1], dp[i-1][j]) + arr[i][j]
print(max(dp[n-1]))
① 먼저 초기의 파이어볼을 입력받은 후에 fireball라는 큐와 graph의 각 칸에 파이어볼을 삽입합니다.
fireball 큐는 현재 존재하는 파이어볼의 위치를 저장하는 큐이고
graph는 N x N 그래프(맵 전체)를 나타냅니다.
이 때, graph의 각 칸에는 그 칸에 존재하는 모든 파이어볼의 정보(질량, 방향, 속력)를 저장합니다.
② 파이어볼을 큐에서 꺼냅니다.
꺼낸 파이어볼의 칸으로 가서 파이어볼 정보를 꺼낸 후(pop) 이 정보를 토대로 파이어볼을 이동 시킵니다.
(이동은 옮길 칸에 정보(m, s, d)를 넣어줍니다.)
이 때, 아직 파이어볼이 합쳐질지 말지는 모르기 때문에 파이어볼큐에는 파이어볼을 넣지 않습니다.
③ 이동이 끝난 후, 파이어볼이 2개 이상 존재하는 칸은
문제에서 제시한 규칙대로 파이어볼을 하나로 합친 후에 4개로 나눕니다.
④ 나누어졌다면 바뀐 정보를 다시 해당 칸에 넣어주고, 위치는 fireball 큐에 삽입합니다.
⑤ 파이어볼이 1개만 존재하는 칸은 그대로 다시 파이어볼에 삽입합니다.
② ~ ⑤ 과정을 K번 반복한 후 정답을 출력하면 됩니다.
from collections import deque
n, m, k = map(int, input().split())
graph = [[deque() for _ in range(n)] for _ in range(n)]
dx = [-1, -1, 0, 1, 1, 1, 0, -1]
dy = [0, 1, 1, 1, 0, -1, -1, -1]
fireball = deque()
for i in range(m):
r, c, m, s, d = map(int, input().split())
fireball.append([r-1, c-1])
graph[r-1][c-1].append(deque([m, s, d]))
for _ in range(k):
for j in range(len(fireball)):
r, c = fireball.popleft()
m, s, d = graph[r][c].popleft()
nr = (r + s*dx[d]) % n
nc = (c + s*dy[d]) % n
graph[nr][nc].append(deque([m, s, d]))
for i in range(n):
for j in range(n):
if len(graph[i][j]) > 1:
sum_m, sum_s, odd_d, even_d, cnt = 0, 0, 0, 0, 0
while graph[i][j]:
m, s, d = graph[i][j].popleft()
sum_m += m
sum_s += s
cnt += 1
if d % 2 == 0:
even_d += 1
else:
odd_d += 1
sum_m //= 5
if sum_m == 0:
continue
sum_s //= cnt
if even_d == cnt or odd_d == cnt:
dir = [0, 2, 4, 6]
else:
dir = [1, 3, 5, 7]
for d in range(4):
fireball.append([i, j])
graph[i][j].append(deque([sum_m, sum_s, dir[d]]))
elif len(graph[i][j]) == 1:
fireball.append([i, j])
answer = 0
for i in range(n):
for j in range(n):
answer += sum(arr[0] for arr in graph[i][j])
print(answer)
문제의 설명이 굉장히 긴 편이라 위 링크의 문제를 꼼꼼히 읽어보시고 풀이과정을 살펴보시길 추천드립니다.
일반적인 BFS/ DFS 문제보다 신경써서 구현해야 할 부분들이 훨씬 까다로운 문제이므로
과정을 하나하나 잘 살펴보면서 구현하시는 것을 추천드립니다.
풀이 과정
먼저 두 방법으로 풀면서 코드를 두 가지로 작성해보았습니다.
코드①은 구현해야 할 부분들을 그대로 나열식으로 작성한 코드이며 길이가 좀 더 깁니다.
코드②는 코드①을 좀더 깔끔하고, 중복되는 코드들을 줄여 정리한 코드입니다.
두 코드 모두 접근 방식은 같습니다.
먼저 공통되는 부분인 rotate(회전)함수와 gravity(중력)함수부터 설명드리자면,
rotate는 반시계(왼쪽)방향으로 90도 회전을 해야 하기 때문에
(0, 0) 좌표는 => (n-1, 0) 좌표로 이동을 하게 되고
(0, 1) 좌표는 => (n-2, 0) 좌표로 이동을 하게 됩니다.
이런식으로 직접 행렬을 그려서 비교해보면
(x, y) 좌표는 => (n-1-y, x) 좌표로 이동함을 알 수 있습니다.
gravity는 벽(-1)이나 경계를 만날 때 까지 아래 빈칸으로 계속 쭉 떨어지게 됩니다.
그래서 밑의 행부터 시작하여 차례대로 while문을 통해 내려갈 수 있는 곳 까지 내려가게 해줍니다.
이제 핵심이 되는 BFS 코드(find_group함수)입니다.
풀이①은 문제에서 조건1에 해당하는
크기가 가장 큰 블록 그룹을 찾는다.
그러한 블록 그룹이 여러 개라면 포함된 무지개 블록의 수가 가장 많은 블록 그룹,
그러한 블록도 여러개라면 기준 블록의 행이 가장 큰 것을,
그 것도 여러개이면 열이 가장 큰 것을 찾는다.
이 부분을 함수 안에 같이 구현을 하였습니다.
while문을 통해 그룹을 지은 다음, 그룹의 크기가 2보다 작으면 그룹을 만들지 않고 return 합니다.
현재 만든 그룹과 최대 그룹을 비교를 해서
현재 만든 그룹이 더 크면 최대 그룹을 바꿔줍니다.
크기가 같다면, 무지개 블록의 수가 많은 블록을 최대 그룹으로 하고
그것마저 같다면 기준행, 열을 비교하여 선정을 하면 됩니다.
이 방법을 모두 find_group 함수 안에 순서대로 작성하였습니다.
코드①
from collections import deque
n, m = map(int, input().split())
graph = []
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]
for i in range(n):
graph.append(list(map(int, input().split())))
def find_group(a, b):
visited = [[False] * n for _ in range(n)]
groupQ = []
if graph[a][b] == -1 or graph[a][b] == -2:
return
if graph[a][b] > 0:
myColor = graph[a][b]
else:
myColor = 0
cnt = 1
queue = deque()
queue.append((a, b))
visited[a][b] = True
while queue:
x, y = queue.popleft()
groupQ.append((x, y))
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if nx < 0 or nx >= n or ny < 0 or ny >= n or visited[nx][ny]:
continue
if graph[nx][ny] == -1 or graph[nx][ny] == -2:
continue
if graph[nx][ny] > 0:
if myColor == 0:
myColor = graph[nx][ny]
elif myColor != graph[nx][ny]:
continue
cnt += 1
queue.append((nx, ny))
visited[nx][ny] = True
if cnt < 2:
return
global groupCnt, maxQ
if cnt > groupCnt:
groupCnt = cnt
maxQ = groupQ
elif cnt == groupCnt:
thisZeroCnt, maxZeroCnt = 0, 0
for i in range(cnt):
if graph[groupQ[i][0]][groupQ[i][1]] == 0:
thisZeroCnt += 1
for i in range(groupCnt):
if graph[maxQ[i][0]][maxQ[i][1]] == 0:
maxZeroCnt += 1
if thisZeroCnt == maxZeroCnt:
groupQ.sort(key=lambda x: x[1])
groupQ.sort(key=lambda x: x[0])
maxQ.sort(key=lambda x: x[1])
maxQ.sort(key=lambda x: x[0])
gx, gy, mx, my = 0, 0, 0, 0
for i in range(cnt):
if graph[groupQ[i][0]][groupQ[i][1]] != 0:
gx = groupQ[i][0]
gy = groupQ[i][1]
break
for i in range(groupCnt):
if graph[maxQ[i][0]][maxQ[i][1]] != 0:
mx = maxQ[i][0]
my = maxQ[i][1]
break
if gx > mx:
maxQ = groupQ
elif gx == mx:
if gy > my:
maxQ = groupQ
elif thisZeroCnt > maxZeroCnt:
maxQ = groupQ
return
def gravity():
for i in range(n-2, -1, -1):
for j in range(n):
if graph[i][j] != -1:
tmp = i
while tmp + 1 < n and graph[tmp+1][j] == -2:
graph[tmp+1][j] = graph[tmp][j]
graph[tmp][j] = -2
tmp += 1
def rotate():
newGraph = [[0] * n for _ in range(n)]
for i in range(n):
for j in range(n):
newGraph[n - 1 - j][i] = graph[i][j]
return newGraph
answer = 0
while True:
groupCnt = 0
maxQ = []
for i in range(n):
for j in range(n):
if graph[i][j] > 0:
find_group(i, j)
if not maxQ:
break
answer += len(maxQ)**2
for x, y in maxQ:
graph[x][y] = -2
gravity()
graph = rotate()
gravity()
print(answer)
코드 1과 다른 부분은 BFS코드(find_group함수)입니다.
코드②은 find_group함수에서는 일단 그룹을 형성하여 그 그룹의 크기와 0(무지개)크기, 일반블록+무지개블록의 좌표를 담은 리스트를 반환을 해주었고
이 리스트들을 하나의 큐에 넣은 후에
정렬을 통해 최대 큐(조건에 맞는 큐)를 선정하였습니다.
또한, visited를 함수 안이 아닌 바깥에 선언을 함으로써, 중복으로 형성하는 그룹을 없앴고
대신, 0칸(무지개)은 다음턴에 다른 그룹들과도 형성될 수 있으므로
다시 미방문 처리를 해주어야 합니다.
코드②
from collections import deque
n, m = map(int, input().split())
graph = []
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]
for i in range(n):
graph.append(list(map(int, input().split())))
def find_group(a, b, color):
queue = deque()
queue.append([a, b])
block_cnt, zero_cnt = 1, 0
blocks = [[a, b]]
zeros = []
while queue:
x, y = queue.popleft()
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if nx < 0 or nx >= n or ny < 0 or ny >= n or visited[nx][ny]:
continue
if graph[nx][ny] == color:
visited[nx][ny] = True
queue.append([nx, ny])
block_cnt += 1
blocks.append([nx, ny])
elif graph[nx][ny] == 0:
visited[nx][ny] = True
queue.append([nx, ny])
block_cnt += 1
zeros.append([nx, ny])
zero_cnt += 1
for x, y in zeros:
visited[x][y] = False
return [block_cnt, zero_cnt, blocks + zeros]
def gravity():
for i in range(n-2, -1, -1):
for j in range(n):
if graph[i][j] != -1:
tmp = i
while tmp + 1 < n and graph[tmp+1][j] == -2:
graph[tmp+1][j] = graph[tmp][j]
graph[tmp][j] = -2
tmp += 1
def rotate():
newGraph = [[0] * n for _ in range(n)]
for i in range(n):
for j in range(n):
newGraph[n - 1 - j][i] = graph[i][j]
return newGraph
answer = 0
while True:
visited = [[False]*n for _ in range(n)]
maxQ = []
for i in range(n):
for j in range(n):
if graph[i][j] > 0 and not visited[i][j]:
visited[i][j] = True
block = find_group(i, j, graph[i][j])
if block[0] >= 2:
maxQ.append(block)
print(maxQ)
maxQ.sort(reverse=True)
if not maxQ:
break
answer += maxQ[0][0]**2
for x, y in maxQ[0][2]:
graph[x][y] = -2
gravity()
graph = rotate()
gravity()
print(graph)
print(answer)
문제의 설명이 굉장히 긴 편이라 위 링크의 문제를 꼼꼼히 읽어보시고 풀이과정을 살펴보시길 추천드립니다.
이 문제는, 특별한 알고리즘 없이 문제에서 주어진 사항을 구현하는 문제이지만
구현해야 하는 부분들이 굉장히 까다로운 문제였습니다
풀이 과정
풀이과정이 굉장히 길기 때문에, 잘 모르시는 부분을 중점으로 보시는 것을 추천드립니다.
① 먼저, 가운데 칸(n//2, n//2)은 상어가 있는 곳이며 여기를 시작으로 하여 토네이도처럼 돌아
각 칸에 인덱스를 붙여줘야 한다.(1, 2, 3... n*n)
이 부분은 indexing함수에서 구현하였다.
② 그리고 상어가 마법을 시전하는데, 이 부분은 magic함수에 구현하였다.
위 아래 왼쪽 오른쪽 4방향중에 1방향과 거리가 주어지며
마법 후 해당 칸의 숫자는 사라진다.
해당칸을 0으로 표현함으로써 사라졌음을 표시하였다.
③ 사라진 후에는 빈 칸만큼 뒷 칸들이 당겨야 하기 때문에 이부분은 fill_blank 함수에 구현하였다.
1번 칸부터 순서대로 돌면서 0인 칸(즉, 빈칸)을 발견하면 그 칸을 blankIdx라는 큐에 넣어준 상태로
빈 칸을 만나지 않았을 때, 큐에서 빈칸의 인덱스를 꺼내어
그 칸에 현재 칸의 수를 넣어주고, 현재 칸은 0으로(빈 상태) 만들어줌으로써 당겨주었다.
모두 당겨질 때 까지 반복한다.
④ 이제, 연속된 숫자가 4칸 이상 존재한다면 그 칸들을 폭발시킨다.
이 부분은 bomb 함수에 구현하였다.
처음에는 저장할 숫자가 없으므로 임시로 -1을 지정하였고
칸을 돌면서 전 칸과 같은 숫자가 발생한다면 카운트를 늘려나간다.
그러다가 저장하고 있는 숫자와 다른 수를 만났을 때, 저장하고 있는 수의 카운트가 4 이상이라면 폭발해야하므로
그 칸들을 모두 0으로 바꿔준다. 그리고 점수계산을 해야 하므로 점수도 함께 저장한다.
⑤ 폭발 후에는 그룹을 지어야 한다.
이 부분은 grouping 함수에 구현하였다.
from collections import deque
n, m = map(int, input().split())
graph = []
cmd = []
score = [0]*3
def indexing():
x, y = n // 2, n // 2
dx = [0, 1, 0, -1]
dy = [-1, 0, 1, 0]
depth = 0
while True:
for i in range(4):
if i % 2 == 0:
depth += 1
for j in range(depth):
x += dx[i]
y += dy[i]
graphIdx.append((x, y))
if x == 0 and y == 0:
return
def magic(dir, dist):
x, y = n // 2, n // 2
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
for i in range(dist):
x += dx[dir]
y += dy[dir]
if x < 0 or x >= n or y < 0 or y >= n:
break
graph[x][y] = 0
fill_blank()
while bomb():
fill_blank()
grouping()
def fill_blank():
blankIdx = deque()
for x, y in graphIdx:
if graph[x][y] == 0:
blankIdx.append((x, y))
elif graph[x][y] > 0 and blankIdx:
nx, ny = blankIdx.popleft()
graph[nx][ny] = graph[x][y]
graph[x][y] = 0
blankIdx.append((x, y))
def bomb():
visited = deque()
cnt = 0
num = -1
flag = False
for x, y in graphIdx:
if num == graph[x][y]:
visited.append((x, y))
cnt += 1
else:
if cnt >= 4:
score[num-1] += cnt
flag = True
while visited:
nx, ny = visited.popleft()
if cnt >= 4:
graph[nx][ny] = 0
num = graph[x][y]
cnt = 1
visited.append((x, y))
return flag
def grouping():
cnt = 1
tmpx, tmpy = graphIdx[0]
num = graph[tmpx][tmpy]
nums = []
for i in range(1, len(graphIdx)):
x, y = graphIdx[i][0], graphIdx[i][1]
if num == graph[x][y]:
cnt += 1
else:
nums.append(cnt)
nums.append(num)
num = graph[x][y]
cnt = 1
idx = 0
for x, y in graphIdx:
if not nums:
break
graph[x][y] = nums[idx]
idx += 1
if idx == len(nums):
break
for i in range(n):
graph.append(list(map(int, input().split())))
for i in range(m):
d, s = map(int, input().split())
cmd.append((d, s))
graphIdx = deque()
indexing()
for a, b in cmd:
magic(a-1, b)
answer = 0
for i in range(3):
answer += (i+1) * score[i]
print(answer)
