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

문제 설명

가장 최근에 나왔던 삼성 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)

[Codility] Lesson4 FrogRiverOne 풀이 Python (0)	2021.06.22
[Codility] Lesson4 PermCheck 풀이 Python (0)	2021.06.21
백준 10423 전기가 부족해 풀이 python (0)	2021.06.13
정올 jungol 2078 13일의 금요일 Java, Python (0)	2021.05.03
백준 16724 피리 부는 사나이 python (0)	2021.04.21