백준 21611 마법사 상어와 블리자드 python

문제로이동

21611번: 마법사 상어와 블리자드

---

목차

 

---

 

---

문제 설명

가장 최근에 나왔던 삼성 SW 역량 기출 문제로 알고 있습니다.

약 1시간 15분 가량 소요되었던 문제이며 굉장히 재밌게 풀었습니다만 시간을 좀 더 단축해야겠다는 생각이 강하게 들었습니다.

이번 문제는 각 기능별(함수)로 설명 하겠습니다.

그리고 작동되는 순서는 아래 나열된 순서와 동일합니다.

 

위치별 인덱싱

이 문제를 해결하면서 상어를 중심으로 소용돌이 모양으로 구슬을 이동하고, 변화하고, 폭발하고의 과정이 거쳐지는 것을 알 수 있습니다.

그래서 각 좌표별로 번호를 매겨주었습니다.

공간별 인덱싱

이 인덱싱으로 아래의 모든 함수(구슬의 이동, 변화, 폭파)를 쉽게 구현할 수 있었습니다.

N의 크기가 작아서 python의 dictionary(Java는 hashmap)를 사용했고 인덱싱이 끝난 변수는 아래와 같이 값이 들어가게 됩니다.

 

N=5일 때 인덱싱

중심좌표인 상어의 위치(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

#