꼬리잡기 놀이 [삼성 기출]

1. 문제 접근 방법

- 이 문제의 경우는, 한 번 테스트 케이스를 틀렸다가, 수정해서 맞았다.

-> 꼬리잡기를 할 때, 1과 3이 맞닿아 있는 경우가 있다. 

-> 이러한 경우, 내가 작성한 BFS로는 오류가 발생했다.

-> 엣지 케이스를 고안해낼 수 있는 능력은 매우 중요하다. 여기서 성패가 갈린다.

-> 특히, 중요한 것은 어느 부분에서 엣지 케이스가 발생할 수 있는지 사고하는 능력이다.

-> 문제에서 포인트가 되는 부분이 있다. 그 포인트가 되는 부분에서 어떤 케이스가 존재할 수 있는지 

    사고하는 연습을 해야 한다. 

 

 

2. 코드

from collections import deque 

N, M, K = map(int, input().split())

dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

dx2 = [0, -1, 0, 1]
dy2 = [1, 0, -1, 0]

teamInfo = [] 

board = [] 

point = 0 
round = 1 


for i in range(N):
    row = list(map(int, input().split()))
    board.append(row) 



## 팀을 만들어준다.
## 이것은 처음 초기화할 때 사용한다. 
## 처음 초기화할 때 한 번만 진행해야 한다. 
def makeTeam(x, y):
    
    visited = [[False]*N for _ in range(N)]
    
    team = []
    q = deque() 
    team.append([x, y, 1])
    q.append([x,y])
    visited[x][y] = True
    
    
    ## 처음 1인 점에 대하여, 팀을 만들 때, 1,2,2,...3 이런 식으로 리스트에 넣어주므로,
    ## 1의 다음 넣어야 할 점은 항상 2여야 한다. 
    ## 따라서, 처음 1인 점을 기준으로, 2인 점을 찾으면, 그 점을 다시 큐에 넣어준다. 
    x, y = q.popleft()
        
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
            
        if 0<=nx and nx<N and 0<=ny and ny<N and visited[nx][ny] == False and board[nx][ny] == 2:
            visited[nx][ny] = True
            q.append([nx,ny])
            team.append([nx, ny, board[nx][ny]])
    
    
    ## q에 들어 있는 값 하나 하나에 대해, 다음 점을 찾아준다
    ## 1의 다음 점은 2, 2의 다음 점은 2 혹은 3이다. 
    ## 그리고 그 정보를 team 리스트에 바로 넣어준다. 
    while q:
        
        x, y = q.popleft()
        
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            
            if 0<=nx and nx<N and 0<=ny and ny<N and visited[nx][ny] == False and (board[nx][ny] == 2 or board[nx][ny] == 3):
                visited[nx][ny] = True
                q.append([nx,ny])
                team.append([nx, ny, board[nx][ny]])
                
    ## teamInfo 리스트에 team을 더한다.             
    teamInfo.append(team)    
        


## 숫자가 1인 점이 발견되면, 팀을 만들어준다.
def initialize():
    
    for i in range(N):
        for j in range(N):
            if board[i][j] == 1:
                makeTeam(i, j)
    
    
    
## team을 이동시키는 함수이다
## 이 때, team은 순차적으로 저장되어 있으므로,
## 이전 점을 들고다니면, 그 이전 점을 활용해서, 현재 점을 이동시킬 수 있다
## 이 때, 1의 다음 이동 위치에 4뿐만 아니라, 3도 위치할 수 있음을 이해한다. 
def move(team):
    
    
    
    cx = 0
    cy = 0 
    
    for i in range(len(team)):
        
        x = team[i][0]
        y = team[i][1]
        num = team[i][2] 
        
        
        if i == 0:
            
            cx = x
            cy = y
            
            for j in range(4):
                nx = x + dx[j]
                ny = y + dy[j]
                
                if 0<=nx and nx < N and 0<=ny and ny<N and (board[nx][ny] == 3 or board[nx][ny] == 4):
                    team[i][0] = nx
                    team[i][1] = ny
            
       
        else:
           
           sx = team[i][0]
           sy = team[i][1]
           
           team[i][0] = cx
           team[i][1] = cy
           
           cx = sx
           cy = sy 
           
           
    
    
    
def moveAll(): 
    
    
    for i in range(M):
        team = teamInfo[i]
        move(team)
    
    
def update(team):
    
    for x,y,num in team:
        board[x][y] = num 
    
    
def updateBoard(): 
    
    for i in range(N):
        for j in range(N):
            if board[i][j] == 3:
                board[i][j] = 4
                
                
    for i in range(M):
        team = teamInfo[i]
        update(team)
        
    
def updateBoardAfterReverse(num):
    
    for i in range(M):
        if i == num:
            team = teamInfo[i]
            update(team)
    
    
def printBoard(): 
    
    for i in range(N):
        for j in range(N):
            print(board[i][j],end=' ')
        print('', end='\n')
    print('', end='\n')
    

## 공을 던지는 함수이다
## 공을 시작점으로부터 던지면서, 1,2,3 중 하나를 만나면 리턴해준다
## 만나지 않는다면, -1, -1을 리턴한다 
def throwBall(sx, sy, dir):
    
    
    while True:
        
        if 1<=board[sx][sy] and board[sx][sy]<=3:
            return sx, sy
        else:
            nx = sx + dx2[dir]
            ny = sy + dy2[dir]
            
            if 0<=nx and nx<N and 0<=ny and ny<N:
                sx = nx
                sy = ny
            else:
                break
            
    
    return -1, -1 
    
    
## 공을 던지는 시작점과 방향을 찾기 위한 함수이다
## 현재 라운드를 기준으로 curr를 만들고,
## curr에 해당하는 sx, sy를 찾아준다 
def findStartPoint():
    
    global round 
    
    curr = round % (N*4)
    
    sx = 0
    sy = 0
    dir = 0 
    
    
    if 1<=curr and curr<=N:
        sx = 0
        sy = 0
        dir = 0 
        gap = curr-1
        sx += gap
        
        
    elif (N+1)<=curr and curr<=2*N:
        
        sx = N-1
        sy = 0
        dir = 1 
        gap = curr-(N+1)
        sy += gap 
        
    elif 2*N+1<=curr and curr<=3*N:
        
        sx = N-1
        sy = N-1
        dir = 2 
        gap = curr-(2*N+1)
        sx -= gap
        
    ## curr가 0일 때는 따로 판단해주는 것이 매우 중요하다
    ## 이러한 엣지 케이스를 조심해야 한다 
    elif curr == 0 or (3*N+1<=curr and curr<=4*N-1):
        
        if curr == 0:
            sx = 0
            sy = 0
            dir = 3
        else:
            sx = 0
            sy = N-1
            dir = 3 
            gap = curr-(3*N+1)
            sy -= gap 
    
    
    return sx, sy, dir
    
    
## 공에 맞은 점이, 해당 팀 내에서 몇 번째 점인지를 판단하기 위한 함수이다.      
def findOrder(fx, fy):
    
    teamNum = 0
    order = 0 
    
    
    for i in range(len(teamInfo)):
        team = teamInfo[i]
        
        for j in range(len(team)):
            x = team[j][0]
            y = team[j][1] 
            
            if x == fx and y == fy:
                teamNum = i
                order = j+1
    
    
    return teamNum, order
    
    
## 공에 맞은 팀을 뒤집어준다
## 뒤집어줄 때, [::-1]을 사용해서 뒤집어주고, 
## 맨 앞과 맨 뒤의 숫자들을 변경해줘야 한다 
def reverseTeam(num):
    
    for i in range(len(teamInfo)):
        if i == num:
            teamLen = len(teamInfo[i])
            teamInfo[i] = teamInfo[i][::-1]
            teamInfo[i][0][2] = 1
            teamInfo[i][teamLen-1][2] = 3
            break
    
    
## 초기화를 진행하기 위한 함수이다. 
initialize()


while True:
     
    moveAll()
    
    updateBoard()
    
    sx, sy, dir = findStartPoint()
    fx, fy = throwBall(sx, sy, dir)
    
    if not (fx == -1 and fy == -1):
        num, order = findOrder(fx, fy)
        point += order*order
        reverseTeam(num)
        updateBoardAfterReverse(num)
        
    if round == K:
        break
    else:
        round += 1


print(point)