[파이썬] 백준 21610 : 마법사 상어와 비바라기 (골드5)

[파이썬] 백준 21610 : 마법사 상어와 비바라기 (골드5)

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

 

---

문제

 

---

풀이

0. 방향성 생각

그냥 구현문제. 리스트 인덱스 잘 맞춰서 구현해주면 된다.

 

1. 입력 받기

import sys
input = sys.stdin.readline

n,m = map(int,input().split())
arr = [list(map(int,input().split())) for _ in range(n)]
cloud_now = [(0,n-1),(1,n-1),(0,n-2),(1,n-2)]
move = [None,(-1,0),(-1,-1),(0,-1),(1,-1),(1,0),(1,1),(0,1),(-1,1)]

문제 지문에서 주어진대로 (N,1) 이런식으로 쓰면 인덱스 뒤집어져서 틀린다. 나도 알고싶지 않았다.

또 move도 윗방향이라고 +1이 아니라 리스트에서 보면 인덱스가 감소하는 방향이라 -1이라. 이것도 알고싶지 않았다.

 

2. 구름 위치 구하기, 비바라기 시전

for _ in range(m):
    path,dist = map(int,input().split())
    
    cloud_next = []
    for x,y in cloud_now:
        nx = (x + move[path][0]*dist)%n
        ny = (y + move[path][1]*dist)%n
        cloud_next.append((nx,ny))
        
    for x,y in cloud_next:
        arr[y][x] += 1

양쪽이 연결돼서 인덱스는 나머지로 구할 수 있다. 맵 사이즈 5에서는 2,7,12 ... 모두 같다. 모듈러 연산

다음 좌표를 구했으면 cloud_next에 넣고 arr에 접근해서 값을 모두 늘려준다.

 

3. 물 복사 시전, 물 증발

    for x,y in cloud_next:
        count = 0
        for i in (2,4,6,8):
            nx = x + move[i][0]
            ny = y + move[i][1]
            if 0<=nx<n and 0<=ny<n and arr[ny][nx]>0:
                count += 1
        arr[y][x] += count
    
    cloud_next = set(cloud_next)
    cloud_now = []
    for y in range(n):
        for x in range(n):
            if (x,y) not in cloud_next and arr[y][x]>=2:
                arr[y][x] -= 2
                cloud_now.append((x,y))

대각선 방향을 탐색해서 범위 내에 있고 물이 있으면 count를 세주고 인덱스에 접근해서 물복사 값을 업데이트한다.

이후 다음 구름이 생기는 위치는 cloud_next에 없고 물이 2 이상 있는 위치이다.

포함 유무를 체크할때는 집합을 써서 속도를 늘린다.

---

전체코드

import sys
input = sys.stdin.readline

n,m = map(int,input().split())
arr = [list(map(int,input().split())) for _ in range(n)]
cloud_now = [(0,n-1),(1,n-1),(0,n-2),(1,n-2)]
move = [None,(-1,0),(-1,-1),(0,-1),(1,-1),(1,0),(1,1),(0,1),(-1,1)]

for _ in range(m):
    path,dist = map(int,input().split())

    cloud_next = []
    for x,y in cloud_now:
        nx = (x + move[path][0]*dist)%n
        ny = (y + move[path][1]*dist)%n
        cloud_next.append((nx,ny))
    
    for x,y in cloud_next:
        arr[y][x] += 1

    for x,y in cloud_next:
        count = 0
        for i in (2,4,6,8):
            nx = x + move[i][0]
            ny = y + move[i][1]
            if 0<=nx<n and 0<=ny<n and arr[ny][nx]>0:
                count += 1
        arr[y][x] += count
    
    cloud_next = set(cloud_next)
    cloud_now = []
    for y in range(n):
        for x in range(n):
            if (x,y) not in cloud_next and arr[y][x]>=2:
                arr[y][x] -= 2
                cloud_now.append((x,y))

answer = 0
for i in arr:
    answer += sum(i)
print(answer)

 

코멘트

인덱스 실수만 안하면 크게 어렵진 않은 문제

pypy로 풀었음. 조금 다듬으면 안쓰고도 통과 가능할 듯