144. [삼성기출40]Python 백준 21610 마법사 상어와 비바라기 시간초과 관련

안녕하세요 코딩하는 덕구입니다.

파이썬 백준 21610 마법사 상어와 비바라기 입니다.

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

21610번: 마법사 상어와 비바라기

 

저 밑에 AC는 남이 제출한 코드고 위의 AC는 제가 수정해서 제출한 코드입니다.

먼저 문제 접근 풀이 다 같았지만 차이가 딱 하나 있었는데

 

전

#5. 구름 생성
for i in range(N):
    for j in range(N):
        if board[i][j] >= 2:
            if [i, j] not in tmp:
                cloud.append([i, j])
                board[i][j] -= 2

 

후

for i in range(N):
    for j in range(N):
        if board[i][j] >= 2:
            if (i, j) not in tmp:
                cloud.append([i, j])
                board[i][j] -= 2

 

위의 코드를 밑의 코드로 바꾸니 통과가 됐습니다.

찾아보니 튜플, 리스트를 생성할 때 튜플이 거의 두배정도 속도가 빠르더군요.

또한 indexing 속도도 튜플이 근소하게 빠릅니다. 앞으로 굳이 수정할 데이터가 아니라면 tuple을 사용해야겠습니다.

 

배운점 

1. 튜플 리스트의 생성 속도는 튜플이 압도적으로 빠르다.

2. indexing 속도는 튜플이 조금 빠르다.

3. for문에서 바로 변수 선언 가능 (알고는 있었지만 그동안 잘 안씀)

 

문제 접근

단순한 구현문제 입니다.

격자의 연결은 아래와 같이 구현할 수 있습니다.

nx, ny = (x + dx[d] * s) % N, (y + dy[d] * s) % N

 

Python 정답 코드

백준 21610 마법사 상어와 비바라기 코드입니다. 설명은 아래에 있습니다.

 

N, M = map(int, input().split())
board = [list(map(int, input().split())) for _ in range(N)]
move = [tuple(map(int, input().split())) for _ in range(M)]
cloud = [[N - 1, 0], [N - 1, 1], [N - 2, 0], [N - 2, 1]]
dx = [0, 0, -1, -1, -1, 0, 1, 1, 1]
dy = [0, -1, -1, 0, 1, 1, 1, 0, -1]
di_x = [-1, -1, 1, 1]
di_y = [-1, 1, -1, 1]

def solve():
    global cloud
    for d, s in move:
        tmp = []
        for x, y in cloud:
            nx, ny = (x + dx[d] * s) % N, (y + dy[d] * s) % N
            tmp.append((nx, ny)) #1. 구름 이동
            board[nx][ny] += 1 #2. 비내리기

        #3. 구름 사라짐
        cloud = []

        #4. 물복사 버그
        for x, y in tmp:
            for d in range(4):
                nx, ny = di_x[d] + x, di_y[d] + y
                if 0 <= nx < N and 0 <= ny < N:
                    if board[nx][ny] >= 1:
                        board[x][y] += 1

        #5. 구름 생성
        for i in range(N):
            for j in range(N):
                if board[i][j] >= 2:
                    if (i, j) not in tmp:
                        cloud.append([i, j])
                        board[i][j] -= 2

    ans = 0
    for i in range(N):
        for j in range(N):
            ans += board[i][j]
    return ans

print(solve())

 

Python 코드 설명

 먼저 이동 조건에 맞게 구름을 이동시키고 물을 뿌립니다.

def solve():
    global cloud
    for d, s in move:
        tmp = []
        for x, y in cloud:
            nx, ny = (x + dx[d] * s) % N, (y + dy[d] * s) % N
            tmp.append((nx, ny)) #1. 구름 이동
            board[nx][ny] += 1 #2. 비내리기

        #3. 구름 사라짐
        cloud = []

 

 이후 물이 증가한 곳의 대각에 물이 있다면 물을 늘려주고

#4. 물복사 버그
for x, y in tmp:
    for d in range(4):
        nx, ny = di_x[d] + x, di_y[d] + y
        if 0 <= nx < N and 0 <= ny < N:
            if board[nx][ny] >= 1:
                board[x][y] += 1

 

 구름을 생성시켜 1~5를 반복합니다.

#5. 구름 생성
for i in range(N):
    for j in range(N):
        if board[i][j] >= 2:
            if (i, j) not in tmp:
                cloud.append([i, j])
                board[i][j] -= 2

 

m번 이동 후 답을 구해 출력합니다. 

    ans = 0
    for i in range(N):
        for j in range(N):
            ans += board[i][j]
    return ans

print(solve())

백준 21610 마법사 상어와 비바라기 Python 코드였습니다.

감사합니다.