문제
풀이
정답률보고 만만하게 봤으나 결코 그렇게 만만하진 않았던 문제이다. 구현 아이디어를 잘 떠올려야 빠르게 풀 수 있는 문제. 그래도 최근 기출 문제 중에서는 쉬운 편에 속하는 것 같고 제약조건이 많지 않아서 테케만 맞추면 무난하게 정답을 도출해낼 수 있는 문제였던 것 같다 (디버깅을 안해서 너무 행복했다)
해당 문제에서의 key point 는
1. 두 그룹 간 서로 맞닿아 있는 변의 수를 어떻게 구하는가?
2. 십자가, 그리고 부분 정사각형 회전을 어떻게 하는가?
이다. 아래에서 각 포인트에 대해 간략히 살펴보자
1. 두 그룹 간 서로 맞닿아 있는 변의 수 구하기
먼저 동일한 숫자가 상하좌우로 인접해있는 경우를 동일한 그룹으로 본다고 가정했을 때 이를 그룹핑하는 것은 bfs()로 쉽게 처리할 수 있다.
이 때 bfs() 과정 중에 그룹 별 정보 (= [그룹의 독립적인 ID(Num), 그룹을 이루고 있는 숫자 값, 그룹에 속한 칸의 수])를 group 이란 배열에 저장해둔다
def bfs(i,j,groupNum,visited,boardNum):
coordinate=[]
q=deque()
q.append((i,j))
visited[i][j]=1
coordinate.append((i,j))
while q:
y,x = q.popleft()
for dy, dx in d:
Y=dy+y
X=dx+x
if 0<=Y<N and 0<=X<N and not visited[Y][X] and board[Y][X]==boardNum:
visited[Y][X]=1
q.append((Y,X))
coordinate.append((Y,X))
cnt=len(coordinate)
for y,x in coordinate:
group[y][x]=[groupNum,boardNum,cnt]bfs()을 통해 그룹핑 및 그룹별 정보를 기록한 group 배열을 완성시켰다면 그룹 간 맞닿아 있는 변의 수를 구해 조화로움 점수를 계산해보자. -> getPoints()
먼저, 비교할 그룹 2개를 찾기 위해 combinations 함수를 만들어주고 checkGroupLine 함수를 호출한다.
def getPoints():
global groupNum,comb
arr=[i for i in range(1,groupNum+1)]
# 그룹 조합을 찾는다
comb=[]
combinations(2,[],0,arr)
for c in comb:
group1,group2=c
checkGroupLine(group1,group2)def checkGroupLine(group1Num,group2Num):
global total_points
q = deque()
group1Info=[]
group2Info=[]
lineNum = 0
visited = [[0] * N for _ in range(N)]
for i in range(N):
for j in range(N):
if group[i][j][0]==group1Num: # 조건 닿으면 바로 함수 return
group1Info=group[i][j]
# 그룹 간 인접한 변을 찾기 위한 bfs 수행 시작
q.append((i,j))
visited[i][j]=1
while q:
y,x = q.popleft()
for dy, dx in d:
Y=y+dy
X=x+dx
if 0<=Y<N and 0<=X<N and not visited[Y][X]:
if group[Y][X][0]==group1Num:
visited[Y][X]=1
q.append((Y,X))
elif group[Y][X][0]==group2Num:
group2Info=group[Y][X]
# visited[Y][X] = 1
lineNum+=1
if lineNum>0:
total_points+=(group1Info[2]+group2Info[2])*group1Info[1]*group2Info[1]*lineNum
returncheckGroupLine 함수의 매개변수로 두 그룹을 받는다.
맞닿은 변을 찾기 위해 또 한 번 bfs 로직을 사용할 건데, 이 때 하나의 그룹을 기준으로 bfs를 돌려야만 맞닿은 변을 중복없이 정확하게 계산할 수 있다.
bfs 로직은 기본 로직과 동일하지만, 큐에 좌표를 넣을지 결정하는 조건 부분에서 이동하려는 칸이 또 다른 그룹의 칸이라면 lineNum 변수를 1 증가시키는 코드를 추가해주면 된다.
bfs 로직이 끝나면 바로 조화로움 점수를 계산해주면 끝 !
2. 십자가 모양 및 부분 정사각형 회전시키기
이건 사실 별도의 알고리즘이 필요한게 아니라서 규칙을 찾아내기만 하면 쉽게 구현할 수 있는 파트이다. 평소 회전하는 코드를 익혀두면 빠르게 풀 수 있을 것이다.
코드
import copy
from collections import deque
N=int(input())
board=[]
for _ in range(N):
board.append(list(map(int,input().split())))
group=[[[0,0,0] for _ in range(N)] for _ in range(N)] # groupNum, 해당 그룹을 이루고 있는 숫자 값, 전체 변의 개수
d=[(0,-1),(0,1),(1,0),(-1,0)]
def bfs(i,j,groupNum,visited,boardNum):
coordinate=[]
q=deque()
q.append((i,j))
visited[i][j]=1
coordinate.append((i,j))
while q:
y,x = q.popleft()
for dy, dx in d:
Y=dy+y
X=dx+x
if 0<=Y<N and 0<=X<N and not visited[Y][X] and board[Y][X]==boardNum:
visited[Y][X]=1
q.append((Y,X))
coordinate.append((Y,X))
cnt=len(coordinate)
for y,x in coordinate:
group[y][x]=[groupNum,boardNum,cnt]
# 현재 인덱스를 매개변수로 계속 넘겨주어야함
# 순서가 상관없기 때문에 현재 인덱스보다 낮은 인덱스 값은 볼 필요가 없기 때문
comb=[]
def combinations(n, new_arr, cur_idx,origin):
# 순서 상관 X, 중복 X
if len(new_arr) == n:
comb.append(new_arr)
return
for i in range(cur_idx, len(origin)):
combinations(n, new_arr + [origin[i]], i + 1,origin)
total_points=0
def checkGroupLine(group1Num,group2Num):
global total_points
q = deque()
group1Info=[]
group2Info=[]
lineNum = 0
visited = [[0] * N for _ in range(N)]
for i in range(N):
for j in range(N):
if group[i][j][0]==group1Num: # 조건 닿으면 바로 함수 return
group1Info=group[i][j]
# 그룹 간 인접한 변을 찾기 위한 bfs 수행 시작
q.append((i,j))
visited[i][j]=1
while q:
y,x = q.popleft()
for dy, dx in d:
Y=y+dy
X=x+dx
if 0<=Y<N and 0<=X<N and not visited[Y][X]:
if group[Y][X][0]==group1Num:
visited[Y][X]=1
q.append((Y,X))
elif group[Y][X][0]==group2Num:
group2Info=group[Y][X]
# visited[Y][X] = 1
lineNum+=1
if lineNum>0:
total_points+=(group1Info[2]+group2Info[2])*group1Info[1]*group2Info[1]*lineNum
return
def getPoints():
global groupNum,comb
arr=[i for i in range(1,groupNum+1)]
# 그룹 조합을 찾는다
comb=[]
combinations(2,[],0,arr)
for c in comb:
group1,group2=c
checkGroupLine(group1,group2)
def plus_rotate(): # 십자가 모양 반시계 방향 회전
for i in range(N):
for j in range(N):
if i == half:
arr[i][j] = board[j][i]
if j == half:
arr[i][j] = board[N-j-1][N-i-1]
def square_rotate(x, y, l): # 부분 정사각형 회전
for i in range(x, x+l):
for j in range(y, y+l):
ox, oy = i - x, j - y # (0, 0)으로 변환
rx, ry = oy, l - ox - 1 # 시계 방향 회전 규칙
arr[rx + x][ry + y] = board[i][j] # 다시 (x,y)를 더해줌
for _ in range(4):
visited=[[0]*N for _ in range(N)]
groupNum=0
# bfs 돌면서 그룹 생성 및 그룹 별 정보를 group 배열에 담기
for i in range(N):
for j in range(N):
if not visited[i][j]:
groupNum+=1
bfs(i,j,groupNum,visited,board[i][j])
getPoints()
arr = [[0] * N for _ in range(N)] # 배열 회전하기 위해 만든 빈 배열
half = N // 2
plus_rotate()
square_rotate(0, 0, half)
square_rotate(0, half + 1, half)
square_rotate(half + 1, 0, half)
square_rotate(half + 1, half + 1, half)
board=copy.deepcopy(arr)
print(total_points)갑자기 풀면서 느낀건데 뭔가 직사각형 회전하는 문제가 나올 것 같다 . .
