문제 설명
가장 최근에 나왔던 삼성 SW 역량 기출 문제로 알고 있습니다.
약 1시간 15분 가량 소요되었던 문제이며 굉장히 재밌게 풀었습니다만 시간을 좀 더 단축해야겠다는 생각이 강하게 들었습니다.
이번 문제는 각 기능별(함수)로 설명 하겠습니다.
그리고 작동되는 순서는 아래 나열된 순서와 동일합니다.
위치별 인덱싱
이 문제를 해결하면서 상어를 중심으로 소용돌이 모양으로 구슬을 이동하고, 변화하고, 폭발하고의 과정이 거쳐지는 것을 알 수 있습니다.
그래서 각 좌표별로 번호를 매겨주었습니다.
이 인덱싱으로 아래의 모든 함수(구슬의 이동, 변화, 폭파)를 쉽게 구현할 수 있었습니다.
N의 크기가 작아서 python의 dictionary(Java는 hashmap)를 사용했고 인덱싱이 끝난 변수는 아래와 같이 값이 들어가게 됩니다.
중심좌표인 상어의 위치(1번)부터 소용돌이를 그려가며 인덱싱을 최초 1회만 해준다면 그 이후는 인덱스로 접근하면 편하겠죠?
indexing = {}
def init():#각 필드에 번호와 좌표를 매칭시킨다
x = (N+1)//2-1#필드 중심
y = (N+1)//2-1
index = 1 #현재 필드의 번호
turn = 1 #현재 방향
depth = 1 #나아가는 길이(점점 증가)
#서 - 남 // 동 - 북 (3,2,4,1)
#index % 4
# 4(0) = 북
# 1 = 서
# 2 = 남
# 3 = 동
tmpdir = [[0,-1],[-1,0],[0,1],[1,0]]
tmpfield = [[0]*N for _ in range(N)]
cnt=0#같은 방향으로 이동한 횟수
while x>-1 and y>-1:
indexing[index]=[x,y]#번호에 좌표를 넣어줌
tmpfield[y][x]=index
x+=tmpdir[turn][0]
y+=tmpdir[turn][1]
cnt+=1
index+=1
if cnt==depth:#깊이와 동일하게 움직였다면?
if turn in [0,2]:
depth+=1#남, 북일때는 depth 증가
turn=(turn+1)%4#방향 전환
cnt=0
상어로부터 시작하는 소용돌이의 규칙을 보면 서-남-동-북의 방향을 반복하되, 길이가 점점 길어지는 것을 알 수 있습니다.
이 길이가 길어지는 기준은 남쪽 이후, 북쪽 이후로 매 번 동일하기 때문에 남, 북 방향일 때 depth를 증가시켜주어 다음번 길이에 반영이 됩니다.
상어의 블리자드
상하좌우 방향과 거리가 주어집니다. 정말 단순하게도 해당 방향으로 거리만큼의 구슬을 제거하면 됩니다.
def blizzard(d,s):#상어의 블리자드
cx = (N+1)//2-1
cy = (N+1)//2-1
for i in range(1,s+1):
nx = cx+direction[d][0]*i
ny = cy+direction[d][1]*i
if field[ny][nx]:
field[ny][nx]=0
구슬의 이동
투 포인터(start,end)를 사용했고 단순하게 빈 공간에 구슬을 하나씩 당겨오는 방법으로 구현했습니다.
def moveMarble():#구슬의 이동
start = 2#시작 인덱스 2
end = 3#다음 인덱스 3로 시작
while start < N*N and end<=N*N:
while start<N*N:#비어있는 필드 찾기
sx,sy = indexing[start]
if not field[sy][sx]:#비어있다면
break
start+=1
else:return#더 이상 빈 칸이 없다
if end<=start:
end = start+1
while end<=N*N:
ex,ey = indexing[end]
if field[ey][ex]:#구슬이 있다면?
break
end+=1
else:return#더이상 당길 구슬이 없다
field[sy][sx]=field[ey][ex]
field[ey][ex]=0
구슬의 폭발
연속된 구슬이 4개 이상일 때 폭발시켜야 합니다. 단, 이 때 폭발되는 구슬들은 정답 출력을 위해 반드시 기록하여야 합니다.
저는 broken_marble이라는 배열을 사용했으며 1번구슬, 2번구슬, 3번구슬의 갯수를 매 번 저장합니다.
def bombMarble():#구슬의 파괴
result = False
start = 2
end = 3
same = 1 #같은 구슬 수 카운팅
while start < N*N and end<=N*N:
sx,sy = indexing[start]
ex,ey = indexing[end]
if field[sy][sx] == field[ey][ex]:#구슬 같으면?
same+=1
end+=1
else:#구슬이 달라졌을때
if same>=4:#동일 구슬 4개 이상은 폭파 대상
result = True #한 번이라도 폭파되면 결과값 True
#start ~ end-1까지 폭파한다
for i in range(start,end):
bx,by = indexing[i]
broken_marble[field[by][bx]-1]+=1#폭파되는 구슬 카운팅
field[by][bx]=0#폭파
same=1
start=end
end=start+1
return result#False라는건 더이상 폭파할 구슬이 없다는 뜻
여기서 return으로 True/False를 반환하게 되는데, 폭발이 일어났다는 뜻은 구슬을 당겨야(moveMarble)하기 때문입니다.
반대로, 폭발이 일어나지 않았다면 더 이상 구슬을 이동할 필요가 없다는 뜻이기도 합니다.
구슬의 변화
def changeMarble():#구슬의 변화
newfield = [[0]*N for _ in range(N)]
index = 2
start = 2
end = 3
same = 1
#그룹에 대한 구슬 정의 -> A : 구슬의 갯수, B : 구슬의 번호
while start < N*N and end<=N*N:
sx,sy = indexing[start]
ex,ey = indexing[end]
if field[sy][sx] == field[ey][ex]:#구슬 같으면?
same+=1
end+=1
else:#구슬이 달라졌을때
ix,iy = indexing[index]
newfield[iy][ix] = same #A:구슬갯수
ix,iy = indexing[index+1]
newfield[iy][ix] = field[sy][sx]#B:구슬번호
index+=2
same=1
start=end
end=start+1
if index>N*N:
break
for i in range(N):
for j in range(N):
field[i][j] = newfield[i][j]
구슬의 변화는 현재 field에 즉각 반영하기 보다는 새로운 newfield에 반영하여 복사하는 방식을 선택했습니다.
소스 코드
Python
import sys
input = sys.stdin.readline
N,M = map(int,input().split())
field = [list(map(int,input().strip().split())) for _ in range(N)]
skills = [list(map(int,input().strip().split())) for _ in range(M)]#상어 스킬
direction = [[0,0],[0,-1],[0,1],[-1,0],[1,0]]#상하좌우
broken_marble = [0,0,0]#파괴한 구슬의 수
indexing = {}
def init():#각 필드에 번호와 좌표를 매칭시킨다
x = (N+1)//2-1#필드 중심
y = (N+1)//2-1
index = 1
turn = 1 #현재 방향
depth = 1
#서 - 남 // 동 - 북 (3,2,4,1)
#index % 4
# 4(0) = 북
# 1 = 서
# 2 = 남
# 3 = 동
tmpdir = [[0,-1],[-1,0],[0,1],[1,0]]
tmpfield = [[0]*N for _ in range(N)]
cnt=0#같은 방향으로 이동한 횟수
while x>-1 and y>-1:
indexing[index]=[x,y]#번호에 좌표를 넣어줌
tmpfield[y][x]=index
x+=tmpdir[turn][0]
y+=tmpdir[turn][1]
cnt+=1
index+=1
if cnt==depth:#깊이와 동일하게 움직였다면?
if turn in [0,2]:
depth+=1#남, 북일때는 depth 증가
turn=(turn+1)%4#방향 전환
cnt=0
def changeMarble():#구슬의 변화
newfield = [[0]*N for _ in range(N)]
index = 2
start = 2
end = 3
same = 1
#그룹에 대한 구슬 정의 -> A : 구슬의 갯수, B : 구슬의 번호
while start < N*N and end<=N*N:
sx,sy = indexing[start]
ex,ey = indexing[end]
if field[sy][sx] == field[ey][ex]:#구슬 같으면?
same+=1
end+=1
else:#구슬이 달라졌을때
ix,iy = indexing[index]
newfield[iy][ix] = same #A:구슬갯수
ix,iy = indexing[index+1]
newfield[iy][ix] = field[sy][sx]#B:구슬번호
index+=2
same=1
start=end
end=start+1
if index>N*N:
break
for i in range(N):
for j in range(N):
field[i][j] = newfield[i][j]
#연속하는 구슬이 4개 이상일 때 파괴된다.
def bombMarble():#구슬의 파괴
result = False
start = 2
end = 3
same = 1 #같은 구슬 수 카운팅
while start < N*N and end<=N*N:
sx,sy = indexing[start]
ex,ey = indexing[end]
if field[sy][sx] == field[ey][ex]:#구슬 같으면?
same+=1
end+=1
else:#구슬이 달라졌을때
if same>=4:#동일 구슬 4개 이상은 폭파 대상
result = True #한 번이라도 폭파되면 결과값 True
#start ~ end-1까지 폭파한다
for i in range(start,end):
bx,by = indexing[i]
broken_marble[field[by][bx]-1]+=1#폭파되는 구슬 카운팅
field[by][bx]=0#폭파
same=1
start=end
end=start+1
return result#False라는건 더이상 폭파할 구슬이 없다는 뜻
def moveMarble():#구슬의 이동
start = 2#시작 인덱스 2
end = 3#다음 인덱스 3로 시작
while start < N*N and end<=N*N:
while start<N*N:#비어있는 필드 찾기
sx,sy = indexing[start]
if not field[sy][sx]:#비어있다면
break
start+=1
else:return#더 이상 빈 칸이 없다
if end<=start:
end = start+1
while end<=N*N:
ex,ey = indexing[end]
if field[ey][ex]:#구슬이 있다면?
break
end+=1
else:return#더이상 당길 구슬이 없다
field[sy][sx]=field[ey][ex]
field[ey][ex]=0
def blizzard(d,s):#상어의 블리자드
cx = (N+1)//2-1
cy = (N+1)//2-1
for i in range(1,s+1):
nx = cx+direction[d][0]*i
ny = cy+direction[d][1]*i
if field[ny][nx]:
# broken_marble[field[ny][nx]-1]+=1 #블리자드로 파괴된 구슬도 합산되는가?
field[ny][nx]=0
def testPrint():
for i in range(N):
for j in range(N):
print(field[i][j],end=' ')
print()
init()
for skill in skills:
d,s = skill
blizzard(d,s)
moveMarble()
while bombMarble():
moveMarble()#이동과 폭파를 반복한다
changeMarble()
print(broken_marble[0]+broken_marble[1]*2+broken_marble[2]*3)Java8
#