문제
문제 설명
rows x columns 크기인 행렬이 있습니다. 행렬에는 1부터 rows x columns까지의 숫자가 한 줄씩 순서대로 적혀있습니다. 이 행렬에서 직사각형 모양의 범위를 여러 번 선택해, 테두리 부분에 있는 숫자들을 시계방향으로 회전시키려 합니다. 각 회전은 (x1, y1, x2, y2)인 정수 4개로 표현하며, 그 의미는 다음과 같습니다.
x1 행 y1 열부터 x2 행 y2 열까지의 영역에 해당하는 직사각형에서 테두리에 있는 숫자들을 한 칸씩 시계방향으로 회전합니다.
제한사항
rows는 2 이상 100 이하인 자연수입니다.
columns는 2 이상 100 이하인 자연수입니다.
처음에 행렬에는 가로 방향으로 숫자가 1부터 하나씩 증가하면서 적혀있습니다.
즉, 아무 회전도 하지 않았을 때, i 행 j 열에 있는 숫자는 ((i-1) x columns + j)입니다.
queries의 행의 개수(회전의 개수)는 1 이상 10,000 이하입니다.
queries의 각 행은 4개의 정수 [x1, y1, x2, y2]입니다.
x1 행 y1 열부터 x2 행 y2 열까지 영역의 테두리를 시계방향으로 회전한다는 뜻입니다.
1 ≤ x1 < x2 ≤ rows, 1 ≤ y1 < y2 ≤ columns입니다.
모든 회전은 순서대로 이루어집니다.
예를 들어, 두 번째 회전에 대한 답은 첫 번째 회전을 실행한 다음, 그 상태에서 두 번째 회전을 실행했을 때 이동한 숫자 중 최솟값을 구하면 됩니다.
입출력 예시
rows columns queries result
6 6 [[2,2,5,4],[3,3,6,6],[5,1,6,3]][8, 10, 25]
3 3 [[1,1,2,2],[1,2,2,3],[2,1,3,2],[2,2,3,3]][1, 1, 5, 3]
100 97 [[1,1,100,97]][1]
입출력 예
정답
graph = []
def turn_find(x,y,nx,ny):
global graph
# 그래프 돌리기
dx = [0,1,0,-1]
dy = [1,0,-1,0]
direction = 0
pos_x, pos_y = x,y
post = 0
prev = graph[x][y]
result = prev
while True:
pos_x ,pos_y = pos_x + dx[direction], pos_y + dy[direction]
if pos_x< x or pos_x > nx or pos_y < y or pos_y > ny:
pos_x -= dx[direction]
pos_y -= dy[direction]
direction += 1
continue
if pos_x == x and pos_y == y:
graph[pos_x][pos_y] = prev
break
post = graph[pos_x][pos_y]
graph[pos_x][pos_y] = prev
if post < result:
result = post
prev= post
return result
def solution(rows, columns, queries):
answer = []
global graph
tmp = []
# 그래프 생성
for i in range(1,rows*columns+1):
tmp.append(i)
if i % columns == 0:
graph.append(tmp)
tmp = []
for x,y,nx,ny in queries:
a = turn_find(x-1,y-1,nx-1,ny-1)
answer.append(a)
return answer풀이
해당은 그래프문제였던 것 같다.
처음에 기본 그래프를 생성해주고 행이 1부터 시작이니 각 행 숫자에 -1 을 시켜주었다.
그리고 핵심포인트는 direction을 0으로 설정해서
다음 방향이 만약 원하는 행과 열을 벗어났을 시 다음 방향으로 이동하게 하였다.
출발 지점으로 돌아오면 break를 걸어 탈출하게 하였다.
dx = [0,1,0,-1]
dy = [1,0,-1,0]
그리고 전에 있던 숫자를 채워주고
가장 작은 숫자인지 검사를 진행과 동시에 옮겨주는 작업을 진행하였다.
이렇게 되면 내부를 건들지 않고 테두리만 검사를 진행할 수 있다.
나온 값을 리턴해주면 끝!
해당 문제는 rows,columns 를 헷갈리게 주여져서 문제의 핵심을 파악하는 건 금방했지만 x,y 판단에 시간을 너무 오래 사용한 것 같다 ㅠㅠ
