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

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

반응형

문제로이동

 

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

마법사 상어는 파이어볼, 토네이도, 파이어스톰, 물복사버그, 비바라기 마법을 할 수 있다. 오늘 새로 배운 마법은 블리자드이고, 크기가 N×N인 격자에서 연습하려고 한다. N은 항상 홀수이고, (

www.acmicpc.net


목차

     


     


    문제 설명

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

    #
    반응형