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

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

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

텍스트만 읽어보면

뭔소리인지 감이 안오는 문제.

예시를 보면

이런 식으로 움직인다고 하네요.

이걸 구현하는 건

머릿속에서 바로 떠올랐습니다.

 

1. 구름이 있는 배열을 지정하여

따로 구름을 저정함.

 

2. 구름이 있는 위치를 불러내어

구름을 이동시킨 후, 해당 위치에 +1

 

3. 구름이 없었던 자리에 구름을 소환하고 반복

 

이 문제에서는 구름이 이동할 때

경계를 벗어나도 움직인다는 점을 유의했어야합니다.

 

그리고 추가적으로 제가 실수했던 부분도 있었는데요

처음에는 제 스스로 편의를 위해

구름 각각을 하나씩 옮긴 다음에

그 자리에서 물복사버그를 했습니다.

그랬더니 당연히 결과가 예시와 안 맞았습니다.

아닌 케이스를 위의 그림으로 그려봤는데요

체크한 위치에서 물 복사 버그를 한다고 가정합니다.

원래라면은 

오른쪽 아래 대각선이 1이기 때문에

물복사가 되어야합니다.

하지만 저는 하나씩 옮기고 +1한 다음에

바로 물복사 버그를 시행했기 때문에

체크한 자리에서 물복사를 한 경우에는

0으로 인식되어 카운트 되지 않았습니다.

문제를 읽어보면

'구름이 사라진 뒤에

물복사한다'

라고 되어있기 때문에

코드가 길어지더라도

문제대로 해야합니다.

 

# 21610 마법상어와 비바라기

N, M = map(int, input().split())
graph = [list(map(int, input().split())) for _ in range(N)]
moving = [list(map(int, input().split())) for _ in range(M)]  # 방향 이동거리 순

move_y = [0, -1, -1, -1, 0, 1, 1, 1]
move_x = [-1, -1, 0, 1, 1, 1, 0, -1]  # 움직이는 거리들 구현

copy_y = [-1, -1, 1, 1]
copy_x = [-1, 1, -1, 1]  # 물복사 버그용

cloud = [[False] * N for _ in range(N)]

# 초기 클라우드 값 초기화
cloud[N - 1][0], cloud[N - 1][1], cloud[N - 2][0], cloud[N - 2][1] = True, True, True, True

for i in range(M):
    visited = [[False] * N for _ in range(N)]
    for y in range(N):
        for x in range(N):
            if cloud[y][x] == True:
                n_y = y + move_y[moving[i][0] - 1] * moving[i][1]
                n_x = x + move_x[moving[i][0] - 1] * moving[i][1]
                # 움직인 뒤 경계를 벗어나는 케이스들 정리

                # 반복문을 쓴 이유는, 경계를 많이 벗어나는 케이스들 (작정하고 4N이상을 넘긴다는 식으로)이 있어서
                if n_y < 0:
                    while n_y < 0:
                        n_y += N

                if n_y >= N:
                    while n_y >= N:
                        n_y -= N

                if n_x < 0:
                    while n_x < 0:
                        n_x += N

                if n_x >= N:
                    while n_x >= N:
                        n_x -= N
                # 1증가 후 구름을 없애버림
                visited[n_y][n_x] = True
                graph[n_y][n_x] += 1
                cloud[y][x] = False
    # 물복사버그 시행
    # 처음에는 구름에 1추가하고 바로했는데
    # 그러면 아직 구름이 추가 안된 케이스는 넣지 못하므로
    # 구름이 전부 1 채운 후 시행
    for y in range(N):
        for x in range(N):
            if visited[y][x] == True:
                for k in range(4):
                    c_y = y + copy_y[k]
                    c_x = x + copy_x[k]
                    if (c_y < 0 or c_y >= N) or (c_x < 0 or c_x >= N):
                        continue
                    if graph[c_y][c_x]:
                        graph[y][x] += 1

    # print(cloud)
    # 새로운 구름을 만들기
    for y in range(N):
        for x in range(N):
            if not visited[y][x] and graph[y][x] >= 2:
                cloud[y][x] = True
                graph[y][x] -= 2
    # print(cloud)
    # print(graph)

answer = 0
for y in range(N):
    for x in range(N):
        answer += graph[y][x]

print(answer)

 

체감 난이도가 높지는 않았지만

프로그래밍 시의 주의할 점을

되짚어준 문제였습니다.

 

++++

 

#백준 21610번 마법사 상어와 비바라기


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

cx=[1,1,-1,-1]
cy=[1,-1,1,-1]

N,M=map(int,input().split())

graph=[list(map(int,input().split())) for _ in range(N)]
cloud = [[N - 1, 0], [N - 1, 1], [N - 2, 0], [N - 2, 1]]

for _ in range(M):
    visited=[[False]*N for _ in range(N)]
    d,s=map(int,input().split())
    d-=1
    s=s%N
    m_t=0
    #구룸먼저 이동
    #s 이동 최적화
    while m_t<s:
        for c in cloud:
            c[0]=(c[0]+dx[d])%N
            c[1]=(c[1]+dy[d])%N
        m_t+=1
    #비 내리기
    for x,y in cloud:
        graph[x][y]+=1
        visited[x][y]=True
    #물복사 버그
    for x,y in cloud:
        water=0
        for d in range(4):
            nx=x+cx[d]
            ny=y+cy[d]
            if nx<0 or nx>=N or ny<0 or ny>=N:
                continue
            if graph[nx][ny]>0:
                water+=1
        graph[x][y]+=water
    #새로운 구름 형성
    cloud.clear()
    for x in range(N):
        for y in range(N):
            if graph[x][y]>=2 and not visited[x][y]:
                cloud.append([x,y])
                graph[x][y]-=2


answer=0
for x in range(N):
    for y in range(N):
        answer+=graph[x][y]

print(answer)

이 코드는 위에서와 달리

cloud의 좌표를 바꾼다는 개념으로 접근했습니다.

위에서는 cloud의 위치 전체를

리스트로 받았다면

여기서는 cloud리스트에

각각의 cloud의 위치를 받고 시행했습니다.

시간은 이쪽이 더 걸리며

pypy3로는 통과했지만

python3로는 시간초과가 떴습니다.

시간이 걸린 이유를 생각해보면

구름이 많아지기 시작하면

구름 하나 하나씩 이동하는 방식이

영 좋지 않기 때문입니다.

 

https://jeomn.tistory.com/17

[백준_21610]마법사 상어와 비바라기 with Python

이 코드를 보고 코드를 수정했습니다.

 

#백준 21610번 마법사 상어와 비바라기


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

cx=[1,1,-1,-1]
cy=[1,-1,1,-1]

N,M=map(int,input().split())

graph=[list(map(int,input().split())) for _ in range(N)]
cloud = [[N - 1, 0], [N - 1, 1], [N - 2, 0], [N - 2, 1]]

for _ in range(M):
    visited=[[False]*N for _ in range(N)]
    d,s=map(int,input().split())
    d-=1
    s=s%N
    m_t=0
    #구룸먼저 이동
    #s 이동 최적화
    #s를 곱해주고 N으로 나머지만을 받게 해야 코드가 빨라짐.
    for c in cloud:
        c[0]=(c[0]+s*dx[d])%N
        c[1]=(c[1]+s*dy[d])%N
    #비 내리기
    for x,y in cloud:
        graph[x][y]+=1
        visited[x][y]=True
    #물복사 버그
    for x,y in cloud:
        water=0
        for d in range(4):
            nx=x+cx[d]
            ny=y+cy[d]
            if nx<0 or nx>=N or ny<0 or ny>=N:
                continue
            if graph[nx][ny]>0:
                water+=1
        graph[x][y]+=water
    #새로운 구름 형성
    cloud.clear()
    for x in range(N):
        for y in range(N):
            if graph[x][y]>=2 and not visited[x][y]:
                cloud.append([x,y])
                graph[x][y]-=2


answer=0
for x in range(N):
    for y in range(N):
        answer+=graph[x][y]

print(answer)

위의 코드랑 유사하지만

구름이동부분을 손봤습니다.

이렇게 하면 이동할 때

하나 하나씩 반복문을 돌지 않고

바로 s만큼 이동하게 되면서

범위를 벗어나는 경우도 신경쓸 수 있어

시간절약과 함께 정확도를 높일 수 있었습니다.