[백준/구현] 20057번: 마법사 상어와 토네이도(골드3, python)

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

20057번: 마법사 상어와 토네이도

아이디어

구현해야 할 부분은 두 가지로 아래와 같았다.

1. 전체 맵을 반시계 방향으로 이동

2. 만약 이동한 곳에 모래가 있으면, 흩날리기~

 

# 1. 전체 맵을 반시계 방향으로 이동하기

반시계 방향으로 이동하기 위해서 방향 벡터를 사용하였다.

이렇게 정의해준 뒤, 방향 벡터 리스트 dv를 선언해주었다. 

dv = [(-1, 0), (0, 1), (1, 0), (0, -1)]

 

반시계 방향으로 탐색하는 방법은 아래와 같다.

1. 현재 위치에서 바라보는 방향만 반시계 방향으로 회전

2. 회전한 방향으로 전진

2-1. 만약 전진할 수 없으면 기존 방향으로 전진

2-1-1. 만약 기존 방향으로 전진할 수 없으면 마지막 인덱스이므로 종료

1~2 반복

 

2-1-1은 큐를 사용해서 구현했기 때문에 꼭 필요하지 않아 회색으로 표시 하였다. 

 

구현하기 전 우선 시작 지점과 시작 방향을 설정해주었다.

x, y = N//2, N//2
d = 0

가운데부터 시작하기 때문에 %2를 한 몫만 사용한다. 시작 방향은 위(0)이다.

    while queue:
        x, y, d = queue.popleft()

        # 1. 시계 반대 방향으로 회전
        nd = (d + 3) % 4    

        # 2. 회전한 방향으로 전진
        nx = x + dv[nd][0]
        ny = y + dv[nd][1]

        if 0 <= nx < N and 0 <= ny < N and visited[nx][ny] == 0:
            visited[nx][ny] = 1
            queue.append((nx, ny, nd))

        # 2-1. 회전한 방향으로 전진할 수 없으면 기존 방향으로 전진
        elif nx < 0 or nx >= N or ny < 0 or ny >= N or visited[nx][ny] == 1:
                nx = x + dv[d][0]
                ny = y + dv[d][1]
                if 0 <= nx < N and 0 <= ny < N and visited[nx][ny] == 0:
                    visited[nx][ny] = 1
                    queue.append((nx, ny, d))
                    nd = d
                else:
                     continue

 

#2. 모래 흩날리기

우선 이동한 곳에 모래가 없으면 다음 이동 위치로 넘어간다. 

if board[nx][ny] == 0: continue

 

흩날리는 위치를 알려줄 벡터를 먼저 선언해주었다. 

위 그림처럼 y를 기준으로 0~11까지의 방향을 정하고(빨간 숫자) sv를 만들었다. 

    sv = [(-1,0), (-1,1), (0,1), (1,1), (1,0), (1,-1), (0,-1), (-1,-1), (-2,0), (0,2), (2,0), (0,-2)]

 

그 후, s 리스트에 각각의 값을 담아주었다. (s의 n번째 인덱스의 값은 d가 n일때의 값이다.)

s는 흩날릴 위치(방향)를 담고있다.

이때 해당 위치에 모래의 몇 퍼센트가 날아가는지 모르기 때문에 퍼센트가 작은 곳의 위치부터 순서대로 담아주었다.

그리고 sp 리스트를 추가해서 각각의 퍼센트를 알려주었다.

    # 1% -> 2% -> 5% -> 7% -> 10% -> a 순서
    sp = [1, 1, 2, 2, 5, 7, 7, 10, 10, 0]
    s = [[5, 3, 11, 9, 8, 6, 2, 7, 1, 0],
        [7, 5, 8, 10, 9, 0, 4, 1, 3, 2],
        [7, 1, 9, 11, 10, 6, 2, 5, 3, 4],
        [1, 3, 8, 10, 11, 0, 4, 7, 5, 6]]

 

이후 흩날리는 모래를 계산해주면 된다.

        # 3. 흩날리는 모래 계산
        per = board[nx][ny] / 100
        for idx, sd in enumerate(s[nd]):
            sx = nx + sv[sd][0]
            sy = ny + sv[sd][1]

            if 0 <= sx < N and 0 <= sy < N:
                if sp[idx] == 0: # 알파 자리라면
                    board[sx][sy] += board[nx][ny]
                    board[nx][ny] = 0
                    break
                
                board[sx][sy] += int(per * sp[idx])
                board[nx][ny] -= int(per * sp[idx])
                continue
            
            if sp[idx] == 0: # 알파 자리라면
                answer += board[nx][ny]
                board[nx][ny] = 0
                break

            answer += int(per * sp[idx])
            board[nx][ny] -= int(per * sp[idx])

알파 자리에서는 남은 값을 모두 보내고 nx, ny를 0으로 변경해준다.

 

전체 코드

from collections import deque

def bfs(x, y, d, N, board, visited):
    dv = [(-1, 0), (0, 1), (1, 0), (0, -1)]

    sv = [(-1,0), (-1,1), (0,1), (1,1), (1,0), (1,-1), (0,-1), (-1,-1), (-2,0), (0,2), (2,0), (0,-2)]
    # 1% -> 2% -> 5% -> 7% -> 10% -> a 순서
    sp = [1, 1, 2, 2, 5, 7, 7, 10, 10, 0]
    s = [[5, 3, 11, 9, 8, 6, 2, 7, 1, 0],
        [7, 5, 8, 10, 9, 0, 4, 1, 3, 2],
        [7, 1, 9, 11, 10, 6, 2, 5, 3, 4],
        [1, 3, 8, 10, 11, 0, 4, 7, 5, 6]]
    
    queue = deque([(x, y, d)])
    visited[x][y] = 1
    answer = 0
    while queue:
        x, y, d = queue.popleft()

        # 1. 시계 반대 방향으로 회전
        nd = (d + 3) % 4    

        # 2. 회전한 방향으로 전진
        nx = x + dv[nd][0]
        ny = y + dv[nd][1]

        if 0 <= nx < N and 0 <= ny < N and visited[nx][ny] == 0:
            visited[nx][ny] = 1
            queue.append((nx, ny, nd))

        # 2-1. 회전한 방향으로 전진할 수 없으면 기존 방향으로 전진
        elif nx < 0 or nx >= N or ny < 0 or ny >= N or visited[nx][ny] == 1:
                nx = x + dv[d][0]
                ny = y + dv[d][1]
                if 0 <= nx < N and 0 <= ny < N and visited[nx][ny] == 0:
                    visited[nx][ny] = 1
                    queue.append((nx, ny, d))
                    nd = d
                else:
                     continue
        

        if board[nx][ny] == 0: continue

        # 3. 흩날리는 모래 계산
        per = board[nx][ny] / 100
        for idx, sd in enumerate(s[nd]):
            sx = nx + sv[sd][0]
            sy = ny + sv[sd][1]

            if 0 <= sx < N and 0 <= sy < N:
                if sp[idx] == 0: # 알파 자리라면
                    board[sx][sy] += board[nx][ny]
                    board[nx][ny] = 0
                    break
                
                board[sx][sy] += int(per * sp[idx])
                board[nx][ny] -= int(per * sp[idx])
                continue
            
            if sp[idx] == 0: # 알파 자리라면
                answer += board[nx][ny]
                board[nx][ny] = 0
                break

            answer += int(per * sp[idx])
            board[nx][ny] -= int(per * sp[idx])

    return answer


N = int(input())
board = [[int(x) for x in input().split()] for _ in range(N)]
visited = [[0] * N for _ in range(N)]

# 시작점, 시작 방향
x, y = N//2, N//2
d = 0
print(bfs(x, y, d, N, board, visited))

 

1시간 반 !! 의 결실 ~