삼성 SW 역량테스트 기출
문제
마법사 상어가 토네이도를 배웠고, 오늘은 토네이도를 크기가 N×N인 격자로 나누어진 모래밭에서 연습하려고 한다. 위치 (r, c)는 격자의 r행 c열을 의미하고, A[r][c]는 (r, c)에 있는 모래의 양을 의미한다.
토네이도를 시전하면 격자의 가운데 칸부터 토네이도의 이동이 시작된다. 토네이도는 한 번에 한 칸 이동한다. 다음은 N = 7인 경우 토네이도의 이동이다.
토네이도가 한 칸 이동할 때마다 모래는 다음과 같이 일정한 비율로 흩날리게 된다.
토네이도가 x에서 y로 이동하면, y의 모든 모래가 비율과 α가 적혀있는 칸으로 이동한다. 비율이 적혀있는 칸으로 이동하는 모래의 양은 y에 있는 모래의 해당 비율만큼이고, 계산에서 소수점 아래는 버린다. α로 이동하는 모래의 양은 비율이 적혀있는 칸으로 이동하지 않은 남은 모래의 양과 같다. 모래가 이미 있는 칸으로 모래가 이동하면, 모래의 양은 더해진다. 위의 그림은 토네이도가 왼쪽으로 이동할 때이고, 다른 방향으로 이동하는 경우는 위의 그림을 해당 방향으로 회전하면 된다.
토네이도는 (1, 1)까지 이동한 뒤 소멸한다. 모래가 격자의 밖으로 이동할 수도 있다. 토네이도가 소멸되었을 때, 격자의 밖으로 나간 모래의 양을 구해보자.
풀이
시뮬레이션 문제고 구현으로 풀었다.
문제 풀이의 큰 포인트는 두 가지였던 것 같다.
- 토네이도의 이동 방향과 규칙 찾기 -> move() 메소드로 구현함
- 비율 퍼센테이지를 방향에 맞춰 회전해 적용하기 -> spread() 메소드로 구현함
N = int(input())
graph = [list(map(int, input().split())) for _ in range(N)]
directions = [(0, -1), (1, 0), (0, 1), (-1, 0)]
spread_left = [(-1, 1, 1), (1, 1, 1), (-1, 0, 7), (1, 0, 7), (-1, -1, 10), (1, -1, 10), (0, -2, 5), (-2, 0, 2), (2, 0, 2)] # a -> b에서 b점 좌표 기준 x, y, %
spread_down = [(-1,-1,1), (-1,1,1), (0,1,7), (0,-1,7), (0,-2,2), (0,2,2), (1,-1,10), (1,1,10), (2,0,5)]
spread_right = [(-1,-1,1), (1,-1,1), (-1,0,7), (1,0,7), (-2,0,2), (2,0,2), (-1,1,10), (1,1,10), (0,2,5)]
spread_up = [(1,-1,1), (1,1,1), (0,-1,7), (0,1,7), (0,-2,2), (0,2,2), (-1,-1,10), (-1,1,10), (-2,0,5)]
spread_direction = [spread_left, spread_down, spread_right, spread_up]
alpha = [(0, -1), (1,0), (0,1), (-1,0)]
def move():
ans = 0
length = 1
x, y, d = N//2, N//2, 0
while x != 0:
# 길이만큼 이동
for _ in range(2):
dx, dy = directions[d]
for _ in range(length):
nx, ny = x+dx, y+dy
# 이동으로 인한 모래 뿌리기
x, y = nx, ny
ans += spread(x, y, d)
# print(graph)
# 방향을 길이만큼 가고 나서 바꾸기
d += 1
if d>3:
d %= 4 # 방향은 4로 나눈 나머지로 해야 인덱스가 됨
# 이동거리 증가
length += 1
# while문 탈출하면 length 그대로 해서 한번 더 이동
length -= 1
dx, dy = directions[d]
for _ in range(length):
nx, ny = x+dx, y+dy
x, y = nx, ny
ans += spread(x, y, d)
print(ans)
def spread(x, y, d):
sand = graph[x][y] # 현재 a->b 위치의 모래 양
graph[x][y]=0
left = sand
answer = 0
# 방향에 따라 정해진 비율만큼 모래 버리기
for dx, dy, ratio in spread_direction[d]:
nx, ny, spread_sand = x+dx, y+dy, int(sand*0.01*ratio)
left -= spread_sand # 모래 버리기
# 만약 모래가 격자 밖을 벗어나면, 정답에 추가
if nx < 0 or nx >= N or ny < 0 or ny >= N:
answer += spread_sand
else:
graph[nx][ny] += spread_sand # 흩어진 모래 주변에 추가
# alpha 자리에 남은 모래들 추가
ax, ay = alpha[d]
nx, ny = x+ax, y+ay
if 0 <= nx < N and 0 <= ny < N:
graph[nx][ny] += left
else:
answer += left
return answer
move()
상어 문제들의 공통점인 방향 배열과 dx, dy 테크닉은 기본이고,
주요 포인트인 토네이도의 이동과 모래 흩뿌리기 과정을 잘 구현하는 것이 관건이었다.
사실 모래 뿌리기 비율 배열을 해결해야 하는데 아이디어가 생각이 안 났다.
어차피 네 방향이고 방향이 계속 순환해서 변하기 때문에,
정신 차리고 네 방향 다 그려서 각 방향별 dx, dy, 퍼센테이지를 튜플로 묶은 배열들을 만들어서 풀었다.
당장 시험이 이번주 주말이라 실전이라 생각하고 쌩구현으로 풀었는데 좋은 풀이는 아니었다고 생각한다.
중간에 실수로 하나라도 틀리면 저 많은 배열에서 어디가 틀렸는지를 디버깅하기가 너무 까다롭기 때문이다.
이 메소드를 해결하기 위한 최선의 아이디어는 저 비율 배열 자체를 2차원 리스트로 만들고, 그 2차원 리스트를 회전하는 것이다.
💡 2차원 리스트 90도 회전 (시계 방향)
new_list = list(map(list, zip(*post_list[::-1])))
💡 2차원 리스트 90도 회전 (반시계 방향)
new_list = list(map(list, zip(*post_list)))[::-1]
그리고 모래를 뿌릴 때마다 격자 밖으로 흩어지는 모래들의 양을 계산해야 했는데,
이걸 전역변수로 해결하는 방법을 몰라서 일일이 파라미터로 받고 반환하는 것을 반복했다.
아래와 같이 정답을 전역변수로 선언했다면 덜 고민할 수 있었을 것 같다.
💡
global키워드변수명 앞에 global을 붙이면 전역 접근 가능
