[백준 21611번] 마법사 상어와 블리자드 - python

문제 링크

https://www.acmicpc.net/problem/21611

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

 

풀이 

우선 나의 풀이는 pypy3 으로만 통과한다... 아래에서 python3으로 통과한 사람의 코드와 비교해 볼 예정이다.

구현 문제이고, 흐름은 다음과 같다. 

 

우선, 2차원 배열로 된 graph을 new_graph에 1차원 배열로 바꿔주었다. 

그리고 idx 라는 딕셔너리에 graph 인덱스(key) 별 new_graph의 인덱스(value)를 대입시켜주어 두 배열을 연결시켰다. 

1. 2차원 배열로 이루어진 graph를 1차원 배열로 변경한다. 

- 문제와 같이 소용돌이로 이동하는 방식은 다른 구현 문제에서 풀어본 경험이 있다. 

- 왼쪽 1칸 -> 아래 1칸 -> 오른쪽 2칸 -> 위 2칸 -> 왼쪽 3칸 ... 

- 홀수번째에는 왼쪽으로 i번 이동, 아래로 i번 이동 

- 짝수번째에는 오른쪽으로 i번 이동, 위로 i번 이동

여기서 주의해야할 점은, 마지막 이동이 왼쪽으로 이동하고 한칸 더 가서 중단된다. 즉, new 라는 1차원 배열의 마지막에는 (0,0)이 아닌 (-1,0)이 들어가있다. 따라서 new[:-1] 을 반환한다. 

def init_graph():
    
    # 처음 위치 (중신)
    x = (n-1)//2
    y = (n-1)//2
    
    # 1차원 배열 
    new = []
    # 중심 값  
    new.append(0)
    # 1차원 배열 인덱스 
    idx_cnt = 0
    
    # 2차원 배열 x,y 위치에 대응하는 1차원 배열의 인덱스 값 저장 
    idx[(x,y)] = 0
    
    for i in range(1,n+1):
        # 홀수번째 
        if i % 2 != 0 :
            # 왼쪽 이동 
            for _ in range(i):
                y -= 1
                idx_cnt +=1 
                new.append(graph[x][y])
                idx[(x,y)] = idx_cnt
            # 마지막은 왼쪽만 이동하고 끝남 
            if i == n:
                break
            # 아래 이동 
            for _ in range(i):
                x += 1
                idx_cnt +=1 
                new.append(graph[x][y])
                idx[(x,y)] = idx_cnt
        else :
            # 오른쪽 이동
            for _ in range(i):
                y += 1
                idx_cnt +=1 
                new.append(graph[x][y])
                idx[(x,y)] = idx_cnt
            # 위쪽 이동 
            for _ in range(i):
                x -= 1
                idx_cnt +=1 
                new.append(graph[x][y])
                idx[(x,y)] = idx_cnt

    return new[:-1]

2. m번동안 아래 과정을 반복한다. 

1) 방향 d, 속력 s 만큼 구슬을 파괴한다. 

2차원 배열 graph는, 중심 위치에서 방향 d-1로 s번 이동해서 그 위치를 0으로 만들어주면 된다. 

그리고 파괴된 위치 (x,y)에 대응하는 1차원 배열 new_graph의 위치를 딕셔너리 idx 에서 찾아서 new_graph의 위치도 0으로 만들어준다. 

# 파괴시키는 함수
def power(d, s):
    nx =x 
    ny = y
    for i in range(s):
        nx += dx[d]
        ny += dy[d]
        
        if 0<=nx<n and 0<=ny<n: 
            graph[nx][ny] = 0 
            # 1차원 배열도 0으로
            new_graph[idx[(nx,ny)]] = 0

2) 구슬을 이동시킨다. 

- 해당 과정에서는 1차원 배열만 사용한다. 

1번 인덱스부터 (0번 인덱스는 중심) 앞으로 가면서 다른 구슬을 만날 때까지 한칸씩 이동시켜준다. 

이동하는 위치에 현재 위치 값을 넣고, 현재 위치는 0으로 만들어주면 된다. 

이것 역시 다른 상어 문제들 풀어보면 마주할 수 있다. 

def move(): 

    for i in range(1, n*n):
        if new_graph[i] > 0 :
            r = i-1
            
            while True :
            	# 중심이면 중단 
                if r == 0 :
                    break
                # 다른 구슬 만났음 
                if new_graph[r] > 0 :
                    break 
                # 위치 이동 
                new_graph[r] = new_graph[r+1]
                new_graph[r+1] = 0 
                r-=1

3) 연속으로 4개 이상있는 구슬을 파괴하고 구슬을 이동한다( 2)번 과정 ). 이 과정은 파괴할 구슬이 없을 때까지 반복한다.

이 과정 역시 new_graph(1차원 배열)을 앞에서부터 탐색하면 된다. 

cnt 는 반복되는 횟수, num은 구슬 번호이다. 

따라서 구슬 번호가 같으면 cnt +1 을 해주고,

구슬 번호가 다르면 

- cnt >= 4 라면 구슬 파괴이므로, cnt만큼 해당 위치를 0으로 설정 + 파괴된 구슬 수를 저장한다.

- cnt가 4보다 작다면 cnt =1, num 은 새로운 구슬 번호로 다시 초기화 

구슬 이동은 2)에서 사용한 move 함수를 실행시켜주면 된다. 

def expose():
    i = 0
    
    # 구슬 번호 
    num = new_graph[i]
    # 구슬 개수 
    cnt = 1
    # 파괴된 구슬이 있는지 확인할 flag 
    flag = False 
    while True :
        i += 1 
        # 범위 초과하면 중단 
        if i >= n*n:
            break 
        
        # 같은 구슬 번호 
        if num == new_graph[i]:
            cnt += 1 
        # 구슬 번호가 다르다면 
        else :
            if cnt >= 4 :
                flag = True 
                # 구슬 파괴 
                for j in range(cnt):
                    new_graph[i-1- j] = 0 
                    
                # 파괴된 개수 더하기 
                if num == 1 :
                    result[0] += cnt 
                if num == 2 :
                    result[1] += cnt 
                if num == 3 :
                    result[2] += cnt 
            # 초기화     
            cnt = 1 
            num = new_graph[i]
            
    return flag

4 ) 구슬을 생성한다. 

이것 역시 new_graph를 앞에서부터 확인하면서 3) 과 같이 구슬 번호와 개수를 초기화하고, 

다르다면 추가하고 초기화, 같다면 cnt +1 을 해주었다. 

그리고 0을 만난다면 뒤에도 모두 0이므로 중단 시켜주었다.

새로만든 배열에 길이를 n*n으로 맞춰야하므로 뒤에 0을 추가시켜주고 new_graph를 갱신시켜주었다.

def add():
    tmp_new = [0]
    
    cnt = 1
    num = new_graph[1]

    for i in range(2,n*n):
    	# 현재 위치가 0이라면 뒤에 값 모두 0
        if num == 0:
            break
        
        if num != new_graph[i]:
            tmp_new.append(cnt)
            tmp_new.append(num)
            num = new_graph[i]
            cnt = 1 
            
        else :
            cnt += 1 
     
    # 뒤에 0 추가
    tmp_new += [0] * (n*n - len(tmp_new))
    return tmp_new

5) new_graph에 저장된 현재 구슬 상태를 2차원 배열인 graph에도 기록해준다.

이 과정은 graph를 new_graph로 바꿔줄 때처럼 소용돌이 이동을 하면서 동시에 new_graph의 값을 앞에서부터 차례대로 넣어준다. 

new_graph의 값이 0이라면 뒤에 모두 0이므로 중단 

여기서 중요한 것은, 1번에서와 동일하게 마지막 이동이 왼쪽으로 이동하고 한칸 더 가서 중단된다는 점이다. 따라서 한칸 더 가기 전에 중단시켜줘야 엣지케이스를 통과할 수 있다. 이 부분때문에 애먹었다.. 

def change():
    
    x = (n-1)//2 
    y = (n-1)//2
    new_idx = 0
    
    # 갱신할 2차원 graph
    tmp_graph = [ [0] * n for _ in range(n)]
    
    for i in range(1,n+1):
    	# 현재 위치가 0이라면 뒤에 모두 0이므로 중단 
        if new_graph[new_idx] == 0 :
            break 
        
        if i % 2 :
            # 왼쪽 이동 
            for j in range(i):
                y -= 1 
                new_idx +=1 
                if i == n and j == i-1:
                    return tmp_graph
                    
                tmp_graph[x][y] = new_graph[new_idx]

            # 아래 이동 
            for _ in range(i):
                x += 1 
                new_idx += 1 
                tmp_graph[x][y] = new_graph[new_idx]
        else :
            # 오른쪽 이동 
            for _ in range(i):
                y += 1 
                new_idx +=1 
                tmp_graph[x][y] = new_graph[new_idx]
            # 위 이동 
            for _ in range(i):
                x -= 1 
                new_idx += 1
                tmp_graph[x][y] = new_graph[new_idx]
    
    return tmp_graph

 

전체 코드는 다음과 같다. 

# 폭발된 구슬 개수 저장 
result = [0,0,0]

# 파괴시키는 함수
def power(d, s):
    nx =x 
    ny = y
    for i in range(s):
        nx += dx[d]
        ny += dy[d]
        
        if 0<=nx<n and 0<=ny<n: 
            graph[nx][ny] = 0 
            new_graph[idx[(nx,ny)]] = 0
            
idx = {}
# 일차원 배열로 만듬     
def init_graph():
    
    x = (n-1)//2
    y = (n-1)//2
    new = []
    new.append(0)
    idx_cnt = 0
    idx[(x,y)] = 0
    for i in range(1,n+1):
        if i % 2 != 0 :
            # 왼쪽 이동 
            for _ in range(i):
                y -= 1
                idx_cnt +=1 
                new.append(graph[x][y])
                idx[(x,y)] = idx_cnt
            if i == n:
                break
            # 아래 이동 
            for _ in range(i):
                x += 1
                idx_cnt +=1 
                new.append(graph[x][y])
                idx[(x,y)] = idx_cnt
        else :
            # 오른쪽 이동
            for _ in range(i):
                y += 1
                idx_cnt +=1 
                new.append(graph[x][y])
                idx[(x,y)] = idx_cnt
            # 위쪽 이동 
            for _ in range(i):
                x -= 1
                idx_cnt +=1 
                new.append(graph[x][y])
                idx[(x,y)] = idx_cnt

    return new[:-1] 
    
# 구슬 생성 함수 
def add():
    tmp_new = [0]
    
    cnt = 1
    num = new_graph[1]

    for i in range(2,n*n):
        if num == 0:
            break
        
        if num != new_graph[i]:
            tmp_new.append(cnt)
            tmp_new.append(num)
            num = new_graph[i]
            cnt = 1 
            
        else :
            cnt += 1 
     
    tmp_new += [0] * (n*n - len(tmp_new))
    return tmp_new

# 1차원 배열 -> 2차원 배열 
def change():
    
    x = (n-1)//2 
    y = (n-1)//2
    new_idx = 0
    
    tmp_graph = [ [0] * n for _ in range(n)]
    
    for i in range(1,n+1):
        if new_graph[new_idx] == 0 :
            break 
        
        if i % 2 :
            # 왼쪽 이동 
            for j in range(i):
                y -= 1 
                new_idx +=1 
                if i == n and j == i-1:
                    return tmp_graph
                    
                tmp_graph[x][y] = new_graph[new_idx]

            # 아래 이동 
            for _ in range(i):
                x += 1 
                new_idx += 1 
                tmp_graph[x][y] = new_graph[new_idx]
        else :
            # 오른쪽 이동 
            for _ in range(i):
                y += 1 
                new_idx +=1 
                tmp_graph[x][y] = new_graph[new_idx]
            # 위 이동 
            for _ in range(i):
                x -= 1 
                new_idx += 1
                tmp_graph[x][y] = new_graph[new_idx]
    
    return tmp_graph
 
# 구슬 이동 함수 
def move(): 

    for i in range(1, n*n):
        if new_graph[i] > 0 :
            r = i-1
            
            while True :
                if r == 0 :
                    break
                if new_graph[r] > 0 :
                    break 
                new_graph[r] = new_graph[r+1]
                new_graph[r+1] = 0 
                r-=1 
   
 # 구슬 폭발 함수 
def expose():
    i = 0
    
    num = new_graph[i]
    cnt = 1
    flag = False 
    while True :
        i += 1 
        if i >= n*n:
            break 
        
        if num == new_graph[i]:
            cnt += 1 
        else :
            if cnt >= 4 :
                flag = True 
                for j in range(cnt):
                    new_graph[i-1- j] = 0 
                    
                if num == 1 :
                    result[0] += cnt 
                if num == 2 :
                    result[1] += cnt 
                if num == 3 :
                    result[2] += cnt 
                    
            cnt = 1 
            num = new_graph[i]
            
    return flag
    
n, m = map(int,input().split())

graph = []

for _ in range(n):
    graph.append(list(map(int,input().split())))

magic = []

# 초기 위치 
x = (n-1)//2
y= (n-1) // 2 

for _ in range(m):
    magic.append(list(map(int,input().split())))
    
dx = [-1, 1, 0, 0]
dy = [0,0,-1,1]

new_graph = init_graph()

for i in range(m):
    d = magic[i][0] -1
    s = magic[i][1]
    
    power(d,s)
    move()
    
    while True :
        if not expose():
            break
        move()
    
    new_graph = add()
    graph = change()
    
ans = 1*result[0] + 2*result[1] + 3*result[2]

print(ans)

 

+ python3으로 통과하기 위해서는 move 함수를 수정해줘야 하는데, 수정하니깐 75퍼에서 틀렸다고 나온다... 반례가 뭔지 못찾겠다.

다시 디버깅 해볼 예정 ... 

 

주의할 부분 

1. new_line의 최대 크기는 n*n -1이다. 상어 위치를 제외해야 하기 때문이다. 

2. 구슬이 모두 동일할 때 예외처리 해줘야 한다. 즉, 아래 TC의 답은 6이 나와야 한다. 

5 1
0 0 0 0 0
0 0 1 1 0
0 1 0 1 0
0 1 1 1 0
0 0 0 0 0
1 2

3. 0만 존재할 때 예외처리 해줘야 한다. 

 

다시 푼 코드 

n, m = map(int,input().split())

graph = []
line = []

count_list = [0,0,0]
for _ in range(n):
    graph.append(list(map(int,input().split())))
    
magic = []

dx = [-1,1,0,0]
dy= [0,0,-1,1]

for _ in range(m):
    d,s = map(int,input().split())
    magic.append((d-1,s))
    
def make_line():
    new_line = []
    x = n//2 
    y = n//2 
    for i in range(1,n+1):
        if i % 2 :
            for _ in range(i):
                x += dx[2]
                y += dy[2]
                if y < 0 :
                    return new_line
                
                if graph[x][y] :
                    new_line.append(graph[x][y])
            for _ in range(i):
                x += dx[1]
                y += dy[1]
                if graph[x][y] :
                    new_line.append(graph[x][y])
        else :
            for _ in range(i):
                x += dx[3]
                y += dy[3]
                
                if graph[x][y] :
                    new_line.append(graph[x][y])
            for _ in range(i):
                x += dx[0]
                y += dy[0]
                if graph[x][y] :
                    new_line.append(graph[x][y]) 
    
    
def make_graph():
    x = n//2
    y = n//2
    index = 0 
    new_graph = [ [0] * n for _ in range(n) ]
    for i in range(1,n+1):
        if i % 2 :
            for _ in range(i):
                x += dx[2]
                y += dy[2]
                if y < 0 :
                    return new_graph
                
                if index < len(line):
                    new_graph[x][y] = line[index]
                    index += 1
                else :
                    return new_graph
            for _ in range(i):
                x += dx[1]
                y += dy[1]
                if index < len(line):
                    new_graph[x][y] = line[index]
                    index += 1
                else :
                    return new_graph
        else :
            for _ in range(i):
                x += dx[3]
                y += dy[3]
                if index < len(line):
                    new_graph[x][y] = line[index]
                    index += 1 
                else :
                    return new_graph
                
            for _ in range(i):
                x += dx[0]
                y += dy[0]
                if index < len(line):
                    new_graph[x][y] = line[index]
                    index += 1 
                else :
                    return new_graph
                    
def power(d,s):
    x = n//2
    y = n//2
    for i in range(s):
        x += dx[d]
        y += dy[d]
        
        if x < 0 or x >=n or y < 0 or y >= n :
            return 
    
        if graph[x][y] :
            graph[x][y] = 0 

def remove():
    cnt = 1
    if len(line) == 0 :
        return -1 
    num = line[0]
    new_line = []
    check = False
    for i in range(1,len(line)):
        if num == line[i]:
            cnt +=1 
        else :
            if cnt < 4 :
                for _ in range(cnt):
                    new_line.append(num)
            else :
                count_list[num-1] += cnt 
                check = True
            
            num = line[i]
            cnt = 1 
    
    if cnt > 4 :
        count_list[num-1] += cnt 
        check = True
        return new_line 
    
    for _ in range(cnt):
        new_line.append(num)
    if not check :
        return -1 
    
    return new_line

def add():
    cnt = 1 
    if len(line) == 0 :
        return []
    
    num = line[0]
    new_line = []
    for i in range(1,len(line)):
        if num == line[i]:
            cnt +=1 
        else :
            new_line.append(cnt)
            new_line.append(num)
            
            num = line[i]
            cnt = 1 
    
    new_line.append(cnt)
    new_line.append(num)

    if len(new_line) > n * n -1 :
        new_line = new_line[:n*n-1]

    return new_line
            

line = make_line()

for d,s in magic:
    if len(line) == 0 :
        break 
    power(d,s)
    line = make_line()

    while True :
        result = remove()
        if result == -1 :
            break 
        else :
            line = result 
            
    line = add()
    graph = make_graph()

ans = 1*count_list[0] + 2*count_list[1] + 3 * count_list[2]
print(ans)