🐥 문제 분류
- 시뮬레이션 (구현)
구현 : 풀이를 떠올리는 것은 쉽지만 소스코드로 옮기기 어려운 문제!
구현 문제로 완전탐색과 시뮬레이션이 주로 출제
- 완전탐색 : 모든 경우의 수를 주저 없이 다 계산하는 방법
- 시뮬레이션 : 문제에서 제시한 알고리즘을 한 단계씩 차례대로 직접 수행해야 하는 문제
🐥 문제 링크
- https://www.acmicpc.net/problem/20057
20057번: 마법사 상어와 토네이도
마법사 상어가 토네이도를 배웠고, 오늘은 토네이도를 크기가 N×N인 격자로 나누어진 모래밭에서 연습하려고 한다. 위치 (r, c)는 격자의 r행 c열을 의미하고, A[r][c]는 (r, c)에 있는 모래의 양을
www.acmicpc.net
🐥 문제 설명
마법사 상어가 토네이도를 배웠고, 오늘은 토네이도를 크기가 N×N인 격자로 나누어진 모래밭에서 연습하려고 한다. 위치 (r, c)는 격자의 r행 c열을 의미하고, A[r][c]는 (r, c)에 있는 모래의 양을 의미한다.
토네이도를 시전하면 격자의 가운데 칸부터 토네이도의 이동이 시작된다. 토네이도는 한 번에 한 칸 이동한다. 다음은 N = 7인 경우 토네이도의 이동이다.
토네이도가 한 칸 이동할 때마다 모래는 다음과 같이 일정한 비율로 흩날리게 된다.
토네이도가 x에서 y로 이동하면, y의 모든 모래가 비율과 α가 적혀있는 칸으로 이동한다. 비율이 적혀있는 칸으로 이동하는 모래의 양은 y에 있는 모래의 해당 비율만큼이고, 계산에서 소수점 아래는 버린다. α로 이동하는 모래의 양은 비율이 적혀있는 칸으로 이동하지 않은 남은 모래의 양과 같다. 모래가 이미 있는 칸으로 모래가 이동하면, 모래의 양은 더해진다. 위의 그림은 토네이도가 왼쪽으로 이동할 때이고, 다른 방향으로 이동하는 경우는 위의 그림을 해당 방향으로 회전하면 된다.
토네이도는 (1, 1)까지 이동한 뒤 소멸한다. 모래가 격자의 밖으로 이동할 수도 있다. 토네이도가 소멸되었을 때, 격자의 밖으로 나간 모래의 양을 구해보자.
** 입력 **
첫째 줄에 격자의 크기 N이 주어진다. 둘째 줄부터 N개의 줄에는 격자의 각 칸에 있는 모래가 주어진다. r번째 줄에서 c번째 주어지는 정수는 A[r][c] 이다.
** 출력 **
격자의 밖으로 나간 모래의 양을 출력한다.
** 예제 1 **
| 입력 | 출력 |
| 5 0 0 0 0 0 0 0 0 0 0 0 10 0 0 0 0 0 0 0 0 0 0 0 0 0 |
10 |
** 예제 2 **
| 입력 | 출력 |
| 5 100 200 300 400 500 300 243 432 334 555 999 111 0 999 333 888 777 222 333 900 100 200 300 400 500 |
7501 |
🐥 문제 풀이
- 이 문제의 핵심은 토네이도가 이동한 지점에 모래 이동 비율 판을 잘 적용하는 게 핵심이다!
- 토네이도 방향에 따라 모래 이동 비율 판이 회전되어 적용되여 하며 각 칸에 적용되는 비율의 위치가 변경되게 된다
예로, 왼쪽으로 이동했을 때는 y를 기준으로 위에 있는 부분이 7%가 반영되었다면 아래로 이동할 때에는 y를 기준으로 바로 왼쪽에 있는 부분에 7%가 반영된다! ( 이에 대한 정보를 배열로 가지고 있으면 좋을 듯! )
- 토네이도의 이동은 이동 칸수에 따라 이동 방향이 다르고 각 이동칸수는 2번씩 실행된다는 것이다
쉽게 얘기해서 1칸 이동이 총 2번 발생하는데 이는 왼쪽으로 이동 한번, 아래로 이동 한번이 된다. 이후 2칸 이동 역시 2번 발생하고 이는 오른쪽으로 이동, 위로 이동이 발생한다. 다음으로는 다시 홀수인 3칸 이동이 발생하는데 앞선 1칸 이동과 동일하게 왼쪽과 아래로 이동이 발생한다!
문제의 핵심 과정을 그림으로 표기하면...
토네이도는 왼쪽, 아래, 오른쪽, 위 순서로 수행된다!
'y' 좌표를 기준으로 각 비율이 적힌 좌표로 갈수 있는 좌표를 정의한다!
🐥 문제 풀이 코드
N = int(input())
sand_graph = [ list(map(int, input().split())) for _ in range(N) ]
# 모래 이동 법칙 (x -> y 로 이동하면 y에 있는 모래가 모래판에 비율이 적힌 부분으로 모두 이동 )
# 비율이 적힌 칸을 가는 방법 y를 기준으로!
# ex. left (-2, 0, 0.02)가 의미하는 것은 y 좌표를 기준으로 x는 -2만큼, y는 0만큼 이동한 곳에 비율 0.02를 적용한다는 뜻!
left = [(-2,0, 0.02), (2, 0, 0.02), ( -1, 0, 0.07), (1, 0, 0.07), (-1, -1, 0.1), (1, -1, 0.1), (0, -2, 0.05), (-1, 1, 0.01), (1, 1, 0.01),( 0, -1, 0)]
down = [(-y, x, dis ) for x, y, dis in left ]
right = [(x, -y, dis) for x, y , dis in left]
up = [(y, x, dis) for x, y , dis in left] # 방향에 따라 적용되는 비율의 x,y 위치가 달라짐
rate = {'left': left, 'right': right, 'down': down, 'up': up}
initial = {'s_x' : N//2, 's_y': N//2} # 시작점
ans = 0
def tonado_move(m_x, m_y, cnt, direction): # x_이동 방향, Y_이동 방향, 이동 개수, 방향
global ans
for i in range(cnt): # 상어이동! 상어가 한칸씩 이동할 때마다 토네이도 발생
s_x,s_y = initial['s_x'] + m_x, initial['s_y']+m_y # 이동한 상어 위치
initial['s_x'] , initial['s_y'] = s_x, s_y # 상어 토네이도 이동 정보 업데이트
if s_x < 0 or s_y < 0 : # 종료 조건
break
spread = 0 # 나중에 a에 퍼지지 않고 남은 모래 넣어주기 위해
# 모래이동!
for dx, dy, r in rate[direction]:
nx = s_x + dx
ny = s_y + dy
if r == 0: # a 라는 얘기 남은 모래 전부!
sand = sand_graph[s_x][s_y] - spread
else :
sand = int(sand_graph[s_x][s_y]* r) # 이동할 모래양
spread += sand # 최종 퍼짐 완료
if 0<= nx < N and 0<= ny <N : # 모래의 이동 위치가 그래프 내라면 이동 위치에 모래를 더해주면됨
sand_graph[nx][ny] += sand # 모래 이동
else:
ans += sand # 벗어난 모래
for i in range(1, N+1) :
if i % 2 :# 홀수칸수 이동
tonado_move(0, -1, i , 'left') # 홀수칸 이동시 왼, 아 로만 이동
tonado_move(1, 0 , i , 'down')
else : #짝수칸수 이동
tonado_move(0, 1, i, 'right')
tonado_move(-1, 0, i, 'up')
print(ans)
# 다른 풀이 예시
n = int(input())
data = [list(map(int, input().split())) for _ in range(n)]
x, y = n // 2, n // 2
dx = [0, 1, 0, -1]
dy = [-1, 0, 1, 0]
windx = [
# left
[-1, 1, -2, 2, 0, -1, 1, -1, 1],
# down
[-1, -1, 0, 0, 2, 0, 0, 1, 1],
# right
[1, -1, 2, -2, 0, 1, -1, 1, -1],
# up
[1, 1, 0, 0, -2, 0, 0, -1, -1]
]
windy = [
# left
[1, 1, 0, 0, -2, 0, 0, -1, -1],
# down
[-1, 1, -2, 2, 0, -1, 1, -1, 1],
# right
[-1, -1, 0, 0, 2, 0, 0, 1, 1],
# up
[1, -1, 2, -2, 0, 1, -1, 1, -1]
]
rate = [1, 1, 2, 2, 5, 7, 7, 10, 10]
def wind(x, y, dir) :
value = 0
sand = data[x][y]
sum_value = 0
for i in range(9) :
nx = x + windx[dir][i]
ny = y + windy[dir][i]
wind_sand = (sand * rate[i]) // 100
sum_value += wind_sand
if not (0 <= nx < n and 0 <= ny < n) :
value += wind_sand
continue
data[nx][ny] += wind_sand
nx = x + dx[dir]
ny = y + dy[dir]
a = sand - sum_value
if not (0 <= nx < n and 0 <= ny < n) :
value += a
else :
data[nx][ny] += a
data[x][y] = 0
return value
def solve(x, y) :
value = 0
visited = [[False] * n for _ in range(n)]
dir = -1
while True :
if x == 0 and y == 0 :
break
visited[x][y] = True
nd = (dir + 1) % 4
nx = x + dx[nd]
ny = y + dy[nd]
if visited[nx][ny] :
nd = dir
nx = x + dx[nd]
ny = y + dy[nd]
value += wind(nx, ny, nd)
x, y, dir = nx, ny, nd
return value
result = solve(x, y)
print(result)
👍 참고
- https://www.youtube.com/watch?v=ShmYg75FLE0
추가적으로 2차원 배열을 90도 반시계 방향으로 회전시키는 함수를 만들어서 풀 수도 있음
# 배열을 90도 반시계 방향으로 회전시키는 함수를 만든다.
def rotate_90(proportion):
new_proportion = list(reversed(list(zip(*proportion))))
return new_proportion
# 만든 함수를 사용하여 각각 아래, 오른쪽, 위로 토네이도가 이동할 때의 비율 배열을 만든다.
p = [[0, 0, 0.02, 0, 0],
[0, 0.1, 0.07, 0.01, 0],
[0.05, 0, 0, 0, 0],
[0, 0.1, 0.07, 0.01, 0],
[0, 0, 0.02, 0, 0]]
p1 = rotate_90(p)
p2 = rotate_90(p1)
p3 = rotate_90(p2)
🎯 파이썬 2차원 배열 회전과 관련해서는 아래 링크 참조
- https://www.qu3vipon.com/python-rotate-2d-array
Python 2차원 배열 회전
💬 Intro
www.qu3vipon.com
- https://school.programmers.co.kr/learn/courses/4008/lessons/13318
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
'스터디IT🌼 > Algorithm' 카테고리의 다른 글
| [ DFS / BFS ] 알고리즘 문제 정리 (1) | 2022.10.13 |
|---|---|
| 알아두면 좋은 파이썬 문법 _ for 코딩테스트 (1) | 2022.10.13 |
| [ 프로그래머스 ] 네트워크 _ DFS (0) | 2022.10.09 |
| [ Baekjoon ] 컨베이어 벨트 위의 로봇 _ 구현 (0) | 2022.10.05 |
| [ 파이썬 ] deque 관련 함수 (0) | 2022.10.05 |
댓글