[코드트리] 파이썬 - 꼬리잡기

코드트리 - 꼬리 잡기

# 소요시간 - 100분

# 접근 방법

• s 기업 코딩테스트 대비 구현, 시뮬레이션 문제를 풀게 되었다.
• 문제를 읽으면서 주어진 조건을 요약하고 의사 코드로 작성하면서 눈 여겨본 중요한 키포인트는 아래와 같았다.
  • 사람들을 주어진 경로로 이동시키기
  • 라운드에 따른 공을 던지는 시작점과 방향
  • 공을 맞은 사람의 순서와 뒤집기
• 따라서, 각 팀의 사람들의 위치를 기록할 team_loc리스트와 머리의 위치를 기록할 team_head 딕셔너리를 사용해주었다.
• 주어진 배열을 순회하며 1을 만나는 경우 idx를 팀 번호로 사용하여 bfs 함수를 실행시켜 각 팀의 머리 ~ 꼬리 순서로 기록해주었다.
  • 이 때, 3을 만난 경우는 따로 temp에 저장해둔 후 마지막에 추가해주었다.
  • 2 1 3이나 3 1 2와 같은 경우 3을 만나서 바로 종료해버리는 경우가 있었기 때문에...!
• 이후 move 함수를 실행시켜준다.
  • 각 팀의 사람들을 순회하며 옮겨줄건데, 우선 head에 기록되어 있는 머리의 위치를 si, sj에 저장해주고 4방향을 탐색하며 4를 찾아 준다.
  • 4를 찾았다면 ni, nj에 저장해주고 team_head와 team_loc, arr의 값을 변경해준다.
  • 이제 2번째 사람부터 ni, nj에 현재 위치를 저장하고 si, sj로 이동 후 ni, nj를 4로 변경해준다.
  • 마지막의 경우 3 또는 1이 arr에 기록되어 있기 때문에 무조건 3으로 변경해준다.
  • 이후, head에 기록된 값으로 다시 arr과 team_loc[team][0]번을 변경해주면 된다.
    • 만약 머리와 꼬리에 빈 칸이 없는 경우 3번이 이동 후 1을 4로 변경하기 때문이다..!
• 마지막은 throw함수로 공을 던져준다.
  • 여기서 문제를 꼼꼼히 읽지 않아 많은 시간을 소비하였다.
  • 2n까지는 0에서 시작하지만, 3~4n은 N-1부터 시작하는 것을 놓쳤다..
  • 우선 start => 시작 위치는 n % N으로 구해주고, 방향은 n // N % 4를 통해 구해준다.
  • 이후 방향에 따라 시작 위치를 잡아주고 사람을 만난다면 위치를 바로 return
  • 못 만난다면 -1, -1을 리턴해준다.
• 사람을 만났다면 team_loc를 순회하며 몇 번째 팀에 있는지 찾아주고, 그 팀에서 몇 번째 순서인지 구한 후 result에 제곱만큼 더해준다.
• 이후, team_loc[팀 번호]를 reverse를 이용해 뒤집어주고, team_head와 arr 값을 변경해주면 된다.

from collections import deque  
import sys  
sys.stdin = open('input.txt')  

def bfs(num):  
    visited = [[0] * N for _ in range(N)]  
    bi, bj = team_loc[num][0]  
    visited[bi][bj] = 1  
    q = deque()  
    q.append((bi, bj))  
    temp = []  
    while q:  
        si, sj = q.popleft()  
        for d in range(4):  
            ni, nj = si + di[d], sj + dj[d]  
            if 0<=ni<N and 0<=nj<N and visited[ni][nj] == 0:  
                if arr[ni][nj] == 2:  
                    q.append((ni, nj))  
                    team_loc[num].append([ni, nj])  
                    visited[ni][nj] = 1  
                    break  
                elif arr[ni][nj] == 3:  
                    temp.append([ni, nj])  
    team_loc[num].append(temp[0])  
def move():  
    for idx, t in enumerate(team_loc):  
        # 머리부터 옮겨주기  
        si, sj = team_head[idx]  
        for d in range(4):  
            ni, nj = si+di[d], sj + dj[d]  
            if 0<=ni<N and 0<=nj<N and (arr[ni][nj] == 4 or arr[ni][nj] == 3):  
                arr[ni][nj] = 1  
                arr[si][sj] = 4  
                team_head[idx] = [ni, nj]  
                team_loc[idx][0] = [ni, nj]  
                break  
        for m in range(1, len(t)):  
            ni, nj = team_loc[idx][m]  
            if arr[ni][nj] == 2:  
                arr[si][sj] = 2  
            else:  
                arr[si][sj] = 3  
            arr[ni][nj] = 4  
            team_loc[idx][m] = [si, sj]  
            si, sj = ni, nj  
        hi, hj = team_head[idx]  
        team_loc[idx][0] = [hi, hj]  
        arr[hi][hj] = 1  

def throw(n):  
    # 시작위치와 방향  
    start = n % N  
    d = n // N % 4  
    if d == 0:  
        si, sj = start, 0  
    elif d == 1:  
        si, sj = N-1,start  
    elif d == 2:  
        si, sj = N-1 -start, N-1  
    else:  
        si, sj = 0, N-1-start  

    while 0<=si<N and 0<=sj<N:  
        if arr[si][sj] in [1, 2, 3]:  
            return [si, sj]  
        si += di[d]  
        sj += dj[d]  
    return [-1, -1]  


N, M, K = map(int, input().split())  
arr = [list(map(int, input().split())) for _ in range(N)]  
cnt = 0  
team_loc = [[] for _ in range(M)]  
team_head = dict()  
result = 0  
di, dj = [0, -1, 0, 1], [1, 0, -1, 0]  
# 최초의 팀 기록 해주기  
for i in range(N):  
    for j in range(N):  
        if arr[i][j] == 1:  
            team_loc[cnt].append([i, j])  
            bfs(cnt)  
            team_head[cnt] = [i, j]  
            cnt += 1  
for k in range(K):  
    move()  
    check = throw(k)  
    if not check == [-1, -1]:  
        flag = True  
        for i, c in enumerate(team_loc):  
            if check in c:  
                flag = False  
                for idx, val in enumerate(c):  
                    if check == val:  
                        result += (idx+1) ** 2  
                        break  
                team_loc[i].reverse()  
                team_head[i] = team_loc[i][0]  
                for t in range(len(c)):  
                    ti, tj = team_loc[i][t]  
                    if arr[ti][tj] == 3:  
                        arr[ti][tj] = 1  
                    elif arr[ti][tj] == 1:  
                        arr[ti][tj] = 3  
                    else:  
                        arr[ti][tj] = 2  
            if not flag:  
                break  

print(result)

• 구현 문제 뿐만 아니라 모든 코드를 짤 때 문제 조건을 꼼꼼히 읽고 의사 코드를 탄탄히 짜는게 중요한 것 같다.
• 또한, 의사 코드를 주석으로 옮기면서 다시 한 번 로직을 짜는 것이 오류를 사전에 방지하는 것을 다시 한번 깨달았따..!