꼬리잡기놀이

시키는 대로만 하면 풀리는 문제.. 다만 머리가 꼬리를 쫒는 경우를 나중에 깨달아서 한참 고민했음.

 

import sys, copy
from collections import deque
n, m, k = map(int, sys.stdin.readline().strip().split())
graph = [list(map(int, sys.stdin.readline().strip().split())) for _ in range(n)]
point = 0
teams = deque([])
dx, dy = [1, 0, -1, 0], [0, -1, 0, 1]
turn = 1
is_empty_team = [] 
def plus_score(y, x, team_idx):
    global point, teams, graph, is_empty_team
    team = teams[team_idx]
    point += (team.index((y, x)) + 1) ** 2
    teams[team_idx] = deque(reversed(teams[team_idx]))
    tmp_team = copy.deepcopy(teams[team_idx])
    if is_empty_team[team_idx]:
        y, x = tmp_team.popleft()
        graph[y][x] = 1
        while len(tmp_team) != 2:
            y, x = tmp_team.popleft()
            graph[y][x] = 2
        y, x = tmp_team.popleft()
        graph[y][x] = 3
    else:
        y, x = tmp_team.popleft()
        graph[y][x] = 1
        while len(tmp_team) != 1:
            y, x = tmp_team.popleft()
            graph[y][x] = 2
        y, x = tmp_team.popleft()
        graph[y][x] = 3
def hit_check(y, x):
    global teams
    for team_idx in range(len(teams)):
        team = teams[team_idx]
        if (y, x) in team:
            plus_score(y, x, team_idx)
            return True
    return False


def shoot_ball(d, location):
    global teams, n 
    q = deque([])
    q.append(location)
    while q:
        y, x = q.popleft()
        on_hit = hit_check(y, x)
        if on_hit:
            break
        nx = x + dx[d]
        ny = y + dy[d]
        if nx >= n or nx < 0 or ny >= n or ny < 0:
            continue
        q.append((ny, nx))

    return

def find_ball_direction_location(turn):
    global n
    turn = turn % ( 4 * n )
    if 1 <= turn <= n:
        return 0, (turn - 1, 0)
    elif n + 1 <= turn <= 2 * n:
        return 1, (n - 1, (turn - 1) % n)
    elif 2 * n + 1 <= turn <= 3 * n:
        return 2, ((n - 1) - ((turn - 1) % n) , n - 1)
    elif 3 * n + 1 <= turn <= 4 * n:
        return 3, (0, (n - 1) - ((turn - 1) % n) )
    return 3, (0, (n - 1) - ((turn - 1) % n) )

def find_next_location(y, x, team_idx):
    global dx, dy, graph, n
    for d in range(4):
        nx = x + dx[d]
        ny = y + dy[d]
        if nx >= n or nx < 0 or ny >= n or ny < 0:
            continue
        if graph[ny][nx] == 3:
            tmp_y, tmp_x = ny, nx
        if graph[ny][nx] == 4:
            return ny, nx
    return tmp_y, tmp_x

def move_team(team, team_idx):
    global graph, is_empty_team
    is_empty = True
    moved_team_locations = deque([])
    y, x = team[0]
    ny, nx = find_next_location(y, x, team_idx)
    if graph[ny][nx] == 3:
        is_empty = False
    if is_empty:
        moved_team_locations.append((ny, nx))
        graph[ny][nx] = 1
        while len(team) != 2:
            ny, nx = team.popleft()
            moved_team_locations.append((ny, nx))
            graph[ny][nx] = 2
        ny, nx = team.popleft()
        moved_team_locations.append((ny, nx))
        graph[ny][nx] = 3
        graph[team[0][0]][team[0][1]] = 4
    else:
        is_empty_team[team_idx] = False
        team.appendleft(team.pop())
        ny, nx = team.popleft()
        moved_team_locations.append((ny, nx))
        graph[ny][nx] = 1
        while len(team) != 1:
            ny, nx = team.popleft()
            moved_team_locations.append((ny, nx))
            graph[ny][nx] = 2
        ny, nx = team.popleft()
        moved_team_locations.append((ny, nx))
        graph[ny][nx] = 3
    return moved_team_locations

def find_team(y, x):
    global dx, dy, graph, n
    team = deque([])
    team.append((y,x))
    q = deque([])
    q.append((y,x))
    while q:
        y, x = q.popleft()
        check = 0
        for d in range(4):
            nx = x + dx[d]
            ny = y + dy[d]
            if nx >= n or nx < 0 or ny >= n or ny < 0:
                continue
            if graph[ny][nx] == 2 and (ny, nx) not in team:
                team.append((ny, nx))
                q.append((ny, nx))
            if graph[ny][nx] == 3:
                tmp_y = ny
                tmp_x = nx
    team.append((tmp_y, tmp_x))
    return team
def find_heads():
    global graph, teams, is_empty_team

    for y in range(len(graph)):
        for x in range(len(graph[y])):
            if graph[y][x] == 1:
                teams.append(find_team(y, x))
                is_empty_team.append(True)

find_heads()


while k != 0:
    for team_idx in range(len(teams)):
        
        team = teams[team_idx]
        teams[team_idx] = move_team(team, team_idx)

    direction, location = find_ball_direction_location(turn)

    shoot_ball(direction, location)

    turn += 1
    k -= 1

print(point)