developer-ellen
인간 디버거의 로그 찍기
developer-ellen
전체 방문자
오늘
어제
  • 분류 전체보기 (217)
    • 회고록 (0)
    • 취뽀 및 커리어 여정의 Stack (2)
      • SSAFY 7기 (2)
    • 프로그래밍공부 (24)
      • c++ (0)
      • JAVA (3)
      • Spring (5)
      • design pattern (3)
      • BackDB (1)
      • Servlet&JSP (3)
      • Vue (4)
      • JPA (4)
      • Infra (1)
      • Linux (0)
    • AI (3)
      • papers (3)
      • trend (0)
    • 프로젝트진행 (0)
      • 데이터베이스 (0)
      • 서버개발 (0)
      • 인공지능 (0)
      • 하루정리 (0)
    • 포트폴리오 (0)
    • 알고리즘 (158)
      • 알고리즘문풀 (155)
      • 알고리즘공부 (3)
    • 통계공부 (15)
      • 시계열분석 (15)
      • 회귀분석 (0)
    • CS (14)
      • 컴퓨터네트워크 (4)
      • 운영체제 (8)
      • 데이터베이스 (2)
    • 주저리주저리 (0)
      • 필사 (0)
    • 취업관련정보 (0)

블로그 메뉴

  • 홈
  • 태그
  • 방명록

공지사항

인기 글

태그

  • c++ 빌더 패턴
  • 삼성코테기출자바풀이
  • 코테파이썬
  • 통계학
  • BOJ파이썬풀이
  • SW역량테스트파이썬
  • 삼성코테자바준비
  • 삼성코테파이썬준비
  • 데이터분석
  • 삼성코테기출
  • 삼성코테자바꿀팁
  • 시계열
  • 삼성코테준비
  • 삼성코테구현풀이
  • Arima
  • 카카오코테java풀이
  • 삼성코테구현문제추천
  • c++디자인패턴
  • MA모형
  • SW역량테스트파이썬풀이
  • 통계분석
  • 운영체제인터럽트
  • 시계열분석
  • 삼성코테파이썬
  • 삼성코테자바풀이
  • 백준파이썬풀이
  • AR모형
  • ARIMA모형
  • 삼성코테파이썬풀이
  • 카카오코테

최근 댓글

최근 글

티스토리

hELLO · Designed By 정상우.
developer-ellen

인간 디버거의 로그 찍기

알고리즘/알고리즘문풀

BOJ - 마법사 상어와 비바라기 21610번 (python)

2021. 10. 21. 20:41

❓ 문제 - 백준 마법사 상어와 비바라기 21610번 - python 풀이법

 

출처 

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

 

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

마법사 상어는 파이어볼, 토네이도, 파이어스톰, 물복사버그 마법을 할 수 있다. 오늘 새로 배운 마법은 비바라기이다. 비바라기를 시전하면 하늘에 비구름을 만들 수 있다. 오늘은 비바라기

www.acmicpc.net

 

 

 

📝 문제해결법

1. 이 문제는 구현+Queue으로 풀었다.

  • 초기 구름의 위치를 큐에 append한다. 
  • 이동 횟수만큼 cloud로 이동한 구름 위치를 표시하고, 현재 큐에 존재하는 구름들의 위치로 방향과 거리만큼 구름을 이동시킨다. 이 때 0, n-1 행과열은 이어져 있으므로 이동할 거리는 현재위치에서 해당방향으로 이동시킨 후 n으로 나누어준다. 그리고 이동시킨 구름의 위치를 cloud에 1로 변환한다.
  • 구름이 이동한 곳에 비를 뿌려 물의 양을 1증가시킨다.
  • 그 후, 구름이 이동한 곳에 대각선으로 살펴서 물이 들어있는 바구니의 수를 카운트 후, 해당 숫자만큼 바구니에 물을 채워넣어준다.
  • 구름이 이동한 위치를 제외하고, 모든 격자판에 물의 양이 2이상 있으면 물의 양을 2 감소시키고, 구름을 형성하여 q에 형성한 구름의 위치를 append 해준다.
  • 이동횟수 m 만큼 위 과정을 반복하 후, 모든 격자판의 바구니에 들어있는 물의 양을 더해서 출력해준다.

2. 문제 풀면서 느낀점

  • 오타 조심하자 제발제발제발...
  • 0, n-1 의 행과 열이 이어져 있을 때 처리하는 방식을 기억하자

 

💻 소스코드

# 마법사 상어와 비바라기 - BOJ 21610
# 구현 + queue
from collections import deque

n, m = map(int, input().split())
board = [list(map(int, input().split())) for _ in range(n)]
dx = [0, -1, -1, -1, 0, 1, 1, 1]
dy = [-1, -1, 0, 1, 1, 1, 0, -1]

q = deque()
q.append([n-2, 0])
q.append([n-2, 1])
q.append([n-1, 0])
q.append([n-1, 1])

for _ in range(m):
    cloud = [[0]*n for _ in range(n)]
    d, s = map(int, input().split())
    while q:
        x, y = q.popleft()
        nx = (x + dx[d-1]*s) % n
        ny = (y + dy[d-1]*s) % n
        cloud[nx][ny] = 1

    for i in range(n):
        for j in range(n):
            if cloud[i][j] == 1:
                board[i][j] += 1

    for i in range(n):
        for j in range(n):
            if cloud[i][j] == 1:
                x, y = i, j
                cnt = 0
                for k in [1, 3, 5, 7]:
                    nx = x + dx[k]
                    ny = y + dy[k]
                    if 0 <= nx < n and 0 <= ny < n:
                        if board[nx][ny] > 0:
                            cnt += 1
                board[x][y] += cnt

    for i in range(n):
        for j in range(n):
            if board[i][j] >= 2 and cloud[i][j] == 0:
                board[i][j] -= 2
                q.append([i, j])


s = 0
for i in range(n):
    s += sum(board[i])
print(s)

'알고리즘 > 알고리즘문풀' 카테고리의 다른 글

SW Expert Academy - 수영장 (python)  (0) 2021.10.22
SW Expert Academy - 줄기세포배양 (python)  (0) 2021.10.22
BOJ - 상어 중학교 21609번 (python)  (0) 2021.10.21
BOJ - 마법사 상어와 파이어스톰 20058번 (python)  (0) 2021.10.21
BOJ - 마법사 상어와 토네이도 20057번 (python)  (0) 2021.10.21
    '알고리즘/알고리즘문풀' 카테고리의 다른 글
    • SW Expert Academy - 수영장 (python)
    • SW Expert Academy - 줄기세포배양 (python)
    • BOJ - 상어 중학교 21609번 (python)
    • BOJ - 마법사 상어와 파이어스톰 20058번 (python)
    developer-ellen
    developer-ellen

    티스토리툴바