[BOJ][Python] 10157번 - 자리배정 [구현 - 실버 4티어]

알고리즘 태그

[구현]

태그 설명

아이디어를 코드로 바꾸는 능력

 

문제

백준 문제 - 자리배정

링크: 자리배정

문제설명

문제가 너무 길어서 윗부분은 생략했다.🙄

 

일단 문제를 보면 달팽이 배열을 응용한 문제임을 알 수 있다.

다른 방법은 따로 딱히,,,,생각이 나지 않는다.. 

그래서 달팽이 배열을 만들되, 만드는 도중 내가 찾는 값이 나오면 루프를 break시키는 방식으로 진행하였다.

📃 소스코드 및 설명

from collections import deque
N, M = map(int,input().split())
k = int(input())

visited = [[-1] * N for _ in range(M)]

count = 0
# 1번 예제로 예시를 들자면,
# (6,0) 즉 왼쪽 맨 아래부터 시작을 위해서 아래와 같이 지정해주었다.
row = 0 # 행
column = M #열

# 진행방향 즉, 행과 열은 1칸씩 움직이므로 step을 1씩 증가 혹은 감소 시키는 방식으로
# 처리하였다
step = 1 # 한칸씩 이동
column_size = M
row_size = N
search = True
while search:
  if column_size < 1:
    print(0)
    break
  # 행, 열의 사이즈만큼 돌아준다.  
  # 한 바퀴를 돌고, 행 또는 열의 값을 증가/감소 시키면서 
  # 처음에 만들어놨던 vistied라는 배열에 값을 채워준다.
  for _ in range(column_size):
    count+=1
    column-=step
    visited[column][row] = count
    if count == k:
      print(row+1,M-column)
      search = False
  column_size -= 1
  for _ in range(row_size-1):
    count += 1
    row+=step
    visited[column][row] = count
    if count == k:
      print(row+1,M-column)
      search = False
  row_size -= 1
  # 증/감을 위해서 아래와 같이 처리해주었다.
  step = -step

 

참고로, 위에서 행과 열의 변수를 반대로 적었다...

이 점 유의하자.. 항상 행과 열은 순서가 너무 헷갈리는거 같다..

 

해당 루프를 돌면 아래와 같은 배열이 생긴다.

참고로 아래 배열은 내가 찾고자 하는 값이 없을 경우에만 아래와 같이 나온다.

 

만약 도중에 찾는 값이 있다면?

처음에 visited라는 배열에 -1값으로 만들어놔서 찾은 이후에는 값이 따로 저장되지 않는 -1값을 보여준다.