백준 21610 마법사 상어와 비바라기 (파이썬)

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

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

 

조건을 간단하게 정리하면 다음과 같습니다.

'''
1. 각 칸에 바구니, 바구니에 저장할 물의 양 제한 X
2. 1번행과 N 번 열이 연결되어 있음, 즉 맵 벗어나도 상관 x
3. 비바라기 > 맨 아래 1열 2열 맨 아래 위 행 1열 2열 비구름 생성
4. 비 구름을 M 번 이동, 방향 8개, 방향 d, 거리 s,
5. 방향 ←, ↖, ↑, ↗, →, ↘, ↓, ↙


1. 모든 구름 d 방향 s 칸 이동
2. 비구름 칸에 물 1씩 증가
3. 구름 모두 사라짐
4. 2에서 증가한 칸, 물 복사 버그, > 증가한 칸 기준 대각선 방향 거리가 1인 칸에 물이 있는 바구니의 수 만큼 물 증가
 물의 수 X
 a. 경계를 넘어가는 칸 X
 b.
5. 물이 2이 상인 칸 물의 양 2 감소, 구름이 생기는 칸은 3에서 구름이 사라진 칸 X

M 번 이동 후 물의 총 량
'''

실수했던 부분 

1. 처음에만 비 구름이 생성되고 다음부터는 알아서 생긴 비 구름에 의해 맵이 바뀝니다. 비 구름이 맨 아래 1열 2열 맨 아래 위 행 1열 2열에 M번 생성되지 않습니다.

2. 비 구름이 제자리에 있는 것이 아니고 맵 시작과 함께 같이 움직인다.

3. 물을 동시에 내리고 나중에 대각선 찾아야함, 물 내리고 그 위치에서 동시에 대각선 바구니 갯수 더 해주면 안됩니다.

4. 또한 대각선 찾고 바로 물의 양 증가하면 안됩니다. > 바구니 다 확인하고 한번에 더해줘야 합니다.

 

제출 코드

from collections import deque
N, M = map(int, input().split())
arr = []
dx = [0, 0, -1, -1, -1, 0, 1, 1, 1]
dy = [0, -1, -1, 0, 1, 1, 1, 0, -1]
ans = 0
for i in range(N):
    arr.append(list(map(int, input().split())))

cloud = [[0]*N for _ in range(N)]
cloud[N-1][0] = 1
cloud[N-1][1] = 1
cloud[N-2][0] = 1
cloud[N-2][1] = 1

for _ in range(M):
    d, s = map(int, input().split())

    #구름 이동
    temp = []
    for x in range(N):
        for y in range(N):
            if cloud[x][y] == 1:
                cloud[x][y] = 0
                nx, ny = x + s * dx[d], y + s * dy[d]
                nx, ny = nx % N, ny % N
                temp.append([nx, ny])

    for [x, y] in temp:
        cloud[x][y] = 1

    # 물 증가
    basket = [[0]*N for _ in range(N)]
    for x in range(N):
        for y in range(N):
            if cloud[x][y] == 1:
                arr[x][y] += 1

    # 아 물 내리고 나서 대각선 찾기 해야함
    for x in range(N):
        for y in range(N):
            if cloud[x][y] != 1:
                continue
            cnt = 0
            for ddx, ddy in (-1, -1), (-1, 1), (1, -1), (1, 1):
                nx, ny = x + ddx, y + ddy
                if nx < 0 or nx >= N or ny < 0 or ny >= N:
                    continue
                if arr[nx][ny] > 0:
                    cnt += 1
            basket[x][y] = cnt

    #대각선 개수 만큼 물 증가
    for x in range(N):
        for y in range(N):
            # 대각선 개수 만큼 물 증가
            arr[x][y] += basket[x][y]

    for x in range(N):
        for y in range(N):
            if cloud[x][y] == 1:
                cloud[x][y] = 0

            elif arr[x][y] >= 2:
                arr[x][y] -= 2
                cloud[x][y] = 1

for i in range(N):
    for j in range(N):
        ans += arr[i][j]

print(ans)

 

후기

삼성 SW 역량 테스트 기출 문제 중에서 그나마 쉬운 편에 속했던 것 같습니다. 골드 5 이지만 이런 난이도는 초반에 삽질만 안한다면 제 시간내에 완전히 풀 수 있을 것 같아요.

3시간 내에 한 문제라도 완벽하게 풀고 오겠습니다!