[백준] 10157- 자리배정 (Python)

문제 출처:

www.acmicpc.net/problem/10157

10157번: 자리배정

문제 풀이 전략:

• 첫번째 시도 : 모서리에 대한 규칙성이 있을까?
  
  • 문제를 읽어보면 각 모서리들이 전체 격자의 r,c 와 어떠한 연관성이 있다고 판단 되었기 때문에 그 규칙성을 찾아보려고 했다.
  • 물론 찾지 못해서 FAIL
  • 다 풀고나서 이와 비슷한 방법을 찾아보니 달팽이 배열이라는 개념이 있었다. 모서리가 아니라 방향과 증감, idx에 대해서 접근했으면 아마 찾았을 듯하다.
  • 달팽이 배열을 보고난 뒤에 20하반기 오후 삼성 코딩테스트 문제인 마법사 상어와 토네이도 문제 와 매우 흡사하다는 걸 깨달았다. 
• 두번째 시도 : 브루트포스 , 모두 k가 나올때 까지 모두 적어가면서 찾아보자!
  • 문제에 주어진 입력값에 대한 범위를 보면 5<= C,R <= 1000 이고  K는 1<= K <= 10^8 이다. 하지만 주어진 조건에 의해서 C*R 보다 큰 K값이 들어오면 0을 출력하게 되고 K의 최대값은 1000*1000 = 10^6 이다. 때문에 이 문제에 한해서는 완전탐색으로 풀어도 가능할 것이라고 판단하였다.
  • 그다음으로 어떻게 맵을 채울 것인가에 대한 고민을 하였다.
    • 우선 전체 maps를 0으로 채운 뒤 cnt라는 변수를 설정, 채워넣고 +1 하며 maps에 사람(?)을 채워넣었다.
    • 달팽이 배열 같은 경우 한방향으로만 진행하다가 방향을 바꾸는 지점을 알아채는 것이 주요 포인트인데 나같은 경우 방향을 바꾸는 지점 == 범위를 벗어남 or 이미 들어가 있는 곳을 만남 으로 설정하여 코딩 해주었다.
    • 이후 유사 DFS와 비슷한 방식으로 코드를 작성하여 해결하였다. 유사 인 이유는 4방향이 아닌 1방향으로만 이동하니까..?

def move(dir,start,k):
    global maps,r,c
    #아래,오른쪽,위,왼쪽
    dx = [1,0,-1,0]
    dy = [0,1,0,-1]
    cnt=2
    start_x,start_y = start
    maps[start_x][start_y] =1
    stack = [(start_x,start_y)]
    cur_x = cur_y = 0
    while(True):
        #print('while 처음',stack)
        while(stack):
            cur_x,cur_y = stack.pop()
            nx = cur_x +dx[dir]
            ny = cur_y +dy[dir]
            #print(nx,ny,cnt)
            if(nx>=r or nx<0 or ny>=c or ny<0):
                continue
            if(maps[nx][ny]!=0):
                continue
            maps[nx][ny]=cnt
            if (cnt == k):
                return nx + 1, ny + 1
            stack.append((nx,ny))
            cnt+=1

        stack.append((cur_x,cur_y))
        #print('막혀부렷어 다시 넣어',stack)
        if(dir==0):
            dir = 1
        elif(dir==1):
            dir = 2
        elif(dir==2):
            dir =3
        else:
            dir =0

if __name__=="__main__":
    c,r = map(int,input().split())
    k= int(input())

    maps= [[0]*c for _ in range(r)]

    if(k>r*c):
        print(0)
    else:
        if(k==1):
            print(1,1)
        else:
            idx_x ,idx_y = move(0,(0,0),k)
            #print(np.array(maps))
            print(idx_y,idx_x)

 

• 주의할 점
  • 이런 문제에서 많이 헤메는 부분이 x,y 혹은 r,c가 행인지 열인지 잘 구분해야한다. 문제를 제대로 읽었더라도 내가 코딩을 하다가 이부분을 잘못 생각하는 경우가 더러 있는데 이번 문제도 그랬다. 문제에서는 (1,1)이 왼쪽 하단이라고 나와있기 때문에 나는 돌려서 생각하고 나중에 바꿔줘야지 라고 생각하며 했는데 
  • 결과적으로는 (0,0) 좌측상단에서 시작해놓고 x,y를 바꿔서 생각해서(y,x를 출력해야하는데 x,y를 출력하고 있었다) 1번 틀리고, +1을 안해줘서 한번 더 틀렷다. 이부분때문에 "분명 맞는데.." 라는 생각만하고 시간을 20~30분 가량 소비했던 것 같다.
  • 또한 이문제 같은경우 K=1이 들어온 경우를 따로 코딩해주었다. 대부분에서 아주 극단적인 값이 들어올 경우를 생각하며 코딩해주어야 하는 경우가 많다고 느꼇다.