[코테준비] 삼성20. 코드트리: 꼬리잡기놀이 python & 삼성식 출력

728x90

꼬리잡기놀이

링크:https://www.codetree.ai/training-field/frequent-problems/problems/tail-catch-play/description
기출: 삼성 SW 역량테스트 2022 상반기 오후 1번 문제
난이도:골드 1
분류: 시뮬레이션, DFS
직접 푼 여부: Δ (틀 다 짜고, 시간 단축을 위해 코드트리 공식 풀이 봄)
언어: 파이썬

풀이 노트

team_list 구성의 변천사

1. 각 team의 이동선포함 모든 좌표를 list에 담고, start와 end를 표시하려 했다.

이는 공을 던질 때, 어느 플레이어가 공을 받는지, 아니면 못받는지 처리하기 힘들어서 X

2. team_list에 team별 사람이 있는 곳 좌표만 담으려 했다.

사람이 한칸씩 움직이는 것을 처리하기가 힘들어서 X → (1) 이동선 다 넣기 & (2) "머리→꼬리"순서대로 list에 넣기 & (3) 총 사람수 저장하는 list생성

3. 위에 방법대로 하니, 여전히 어떤 사람이 공을 맞는지 알기 어려워서 → map에 표시 !

새로운 map을 만들어서 각 팀당 몇번째 사람인지 표시했다. 사람이 없는 곳은 0! people_map

정답 코드 (코드트리용)💻

아래 삼성 제출 느낌으로 바꿔서 푼 코드도 있다. (테케를 loop으로 돌리기)

# 꼬리잡기놀이
import copy
import sys

input = sys.stdin.readline

# input ------------------------------
n, m, k = map(int, input().split())
ori_map = [list(map(int, input().split())) for _ in range(n)]
# prepare ------------------------------
dr = [1, -1, 0, 0]
dc = [0, 0, 1, -1]


def in_range(r, c):
    """
    해당 좌표(r,c)가 격자 안에 존재 하는지
    :return:  True / False
    """
    if 0 <= r < n and 0 <= c < n:
        return True
    else:
        return False


# [1] make team_index_map & team_list & headtail_list -------------
""" team 위치 표시, team 별 사람 순서 (r,c)"""
team_index_map = [[-1] * n for _ in range(n)]  # 각 위치에 team index 표시 (이동선 위치), team index는 은 0,1,2,3...m
people_map = [[0] * n for _ in range(n)] # 각 위치에 사람 번호 입력 (team은 index map에서)
team_list = [[] for _ in range(m)]  # team 별 머리부터 꼬리 순서로 모든 이동선표시, index
team_len  = [0]*m # 각 index마다 team의 길이 저장
visited = [[False] * n for _ in range(n)]


def dfs(r, c, length, index):
    """
    team index [map]에 표시, team에 사람들 머리부터 순서대로 index저장 [list]
    :param r: row 좌표
    :param c: column 좌표
    :param length: 지금 들어온 좌표까지의 길이
    :param index: 현재 team index
    :return:
    """
    global visited, team_index_map, team_list, team_len, people_map, people_end
    visited[r][c] = True
    team_index_map[r][c] = index
    team_list[index].append((r, c))
    for direction in range(4):
        newr, newc = r + dr[direction], c + dc[direction]
        if not in_range(newr, newc) or visited[newr][newc] or ori_map[newr][newc] == 0:
            continue # 아니면, 다음것 확인
        # (1) 안가봤고 (2) 범위 내, (3) 빈칸이 아니면 - 꼬리면 하나 더 처리하고, 아니면, dfs
        length += 1
        if ori_map[newr][newc] == 3: # 꼬리면, 길이 저장 (index가 아니라 길이.  3이면, 3로저장)
            team_len[index] = length
            people_map[newr][newc] = length
            people_end = True
        if not people_end:
            people_map[newr][newc] = length
        dfs(newr, newc,length, index)
        break  # 하나 찾았으면, 다른 길 가볼 필요 없음 (길은 하나)
    return


index = 0
for i in range(n):
    for j in range(n):
        if not visited[i][j] and ori_map[i][j] == 1:  # 들린 적 없고, head라면, team 탐색 시작
            # (1) visited, team_list, team_index_map update
            visited[i][j] = True
            team_list[index].append((i, j))
            team_index_map[i][j] = index
            length = 1
            people_map[i][j] = length
            people_end=False
            # (2) 이동 방향중에 2꼬리가 아닌 곳부터 시작해서 이동
            for direction in range(4):
                newr, newc = i + dr[direction], j + dc[direction]
                if in_range(newr, newc) and ori_map[newr][newc] == 2:
                    people_map[newr][newc] =2
                    dfs(newr, newc, length+1, index)
                    break
            # (3) dfs 끝나면, 다음 team 찾아서
            index += 1  # 한 탐색이 끝나면, index +1

# # preparing단계를 잘 했는지 확인 해보는 print문
# print(team_index_map)
# print(people_map)
# print(team_list)
# print(team_len)
# # def ------------------------------
def move_one(index):
    """
    팀원 한 칸씩 이동 - 아래 두개 업데이트
    [1] team_list
    [2] people_map
    :param team_index:
    :return:
    """
    global team_list, people_map
    # [1] team_list
    temp = copy.deepcopy(team_list[index])
    team_list[index] = [temp[-1]] + temp[:-1]
    # [2] people_map
    for i, (r,c)  in enumerate(team_list[index]):
        if i+1 <= team_len[index]:
            # 사람 범위 내에 있을 때는 숫자로
            people_map[r][c] =i+1
        else:
            people_map[r][c] = 0

def where_ball(round):
    """
    공이 어느 방향, 몇번째에서 오는지
    :param round: 몇번째 round
    :return: 방향 (0~3), 몇번째(0~n-1)
    """
    ith = round%n
    direction = (round//n)%4
    return direction, ith
def reverse_people(index):
    """
    [1] list 반대
    [2] map 반대 (list를 기반으로)
    :param index: 
    :return: 
    """
    global team_list, people_map
    # [1]
    temp = copy.deepcopy(team_list[index])
    length = team_len[index]
    team_list[index][:length] = reversed(temp[:length])
    team_list[index][length:] =reversed(temp[length:])

    # [2] people_map
    for i, (r,c)  in enumerate(team_list[index]):
        if i+1 <= length:
            # 사람 범위 내에 있을 때는 숫자로
            people_map[r][c] =i+1
        else:
            break

def ball_hit_try(ball_dir, ball_index):
    """
    공 던져서 맞으면, 처리
    :param ball_dir:
    :param ball_index:
    :param point:
    :return: point
    """
    if ball_dir==0:
        # 좌 -> 우 (최소 column)
        for j in range(n):
            if people_map[ball_index][j]>0:
                point = people_map[ball_index][j] * people_map[ball_index][j]
                index = team_index_map[ball_index][j]
                reverse_people(index)
                return point

    elif ball_dir==1:
        # 하 -> 상 (최대 row)
        for i in range(n-1,-1, -1):
            if people_map[i][ball_index]>0:
                point = people_map[i][ball_index] * people_map[i][ball_index]
                index = team_index_map[i][ball_index]
                reverse_people(index)

                return point
    elif ball_dir ==2:
        # 우 -> 좌 (최대 column)
        for j in range(n-1,-1,-1):
            if people_map[n-1-ball_index][j]>0:
                point = people_map[n-1-ball_index][j]* people_map[n-1-ball_index][j]
                index = team_index_map[n-1-ball_index][j]
                reverse_people(index)
                return point

    else:
        # 상 -> 하 (최소 row)
        for i in range(n):
            if people_map[i][n-1-ball_index]>0:
                point = people_map[i][n-1-ball_index] * people_map[i][n-1-ball_index]
                index = team_index_map[i][n-1-ball_index]
                reverse_people(index)
                return point
    return 0

# # main ------------------------------
point = 0
for round in range(k):
    # [1] 한칸 움직이기
    for team_index in range(m):
        move_one(team_index)
    # [2] 공 공격
    ball_dir, ball_index = where_ball(round)  # 공 어디서 던져질지
    point += ball_hit_try(ball_dir, ball_index)  # 공 던지기 - 맞으면, (1) 점수 + (2) 방향 바꾸기

print(point)

정답 코드 (삼성st)💻

SW expert 문제를 보니 아래처럼 테스트 케이스를 돌리며 출력해야했다. 그래서 그렇게 되게 하는 코드를 짜봤다. (삼성에 익숙해지고자)

# 꼬리잡기놀이
import copy
import sys

sys.stdin = open("./input.txt")
input = sys.stdin.readline


# prepare ------------------------------
dr = [1, -1, 0, 0]
dc = [0, 0, 1, -1]

# def -----------------------------------
def in_range(r, c):
    """
    해당 좌표(r,c)가 격자 안에 존재 하는지
    :return:  True / False
    """
    if 0 <= r < n and 0 <= c < n:
        return True
    else:
        return False

def dfs(r, c, length, index):
    """
    team index [map]에 표시, team에 사람들 머리부터 순서대로 index저장 [list]
    :param r: row 좌표
    :param c: column 좌표
    :param length: 지금 들어온 좌표까지의 길이
    :param index: 현재 team index
    :return:
    """
    global visited, team_index_map, team_list, team_len, people_map, people_end
    visited[r][c] = True
    team_index_map[r][c] = index
    team_list[index].append((r, c))
    for direction in range(4):
        newr, newc = r + dr[direction], c + dc[direction]
        if not in_range(newr, newc) or visited[newr][newc] or ori_map[newr][newc] == 0:
            continue # 아니면, 다음것 확인
        # (1) 안가봤고 (2) 범위 내, (3) 빈칸이 아니면 - 꼬리면 하나 더 처리하고, 아니면, dfs
        length += 1
        if ori_map[newr][newc] == 3: # 꼬리면, 길이 저장 (index가 아니라 길이.  3이면, 3로저장)
            team_len[index] = length
            people_map[newr][newc] = length
            people_end = True
        if not people_end:
            people_map[newr][newc] = length
        dfs(newr, newc,length, index)
        break  # 하나 찾았으면, 다른 길 가볼 필요 없음 (길은 하나)
    return
def dfs_cover():
    """ team 위치 표시, team 별 사람 순서 (r,c)"""
    global index, visited, team_index_map, team_list, people_map, people_end
    for i in range(n):
        for j in range(n):
            if not visited[i][j] and ori_map[i][j] == 1:  # 들린 적 없고, head라면, team 탐색 시작
                # (1) visited, team_list, team_index_map update
                visited[i][j] = True
                team_list[index].append((i, j))
                team_index_map[i][j] = index
                length = 1
                people_map[i][j] = length
                people_end=False
                # (2) 이동 방향중에 2꼬리가 아닌 곳부터 시작해서 이동
                for direction in range(4):
                    newr, newc = i + dr[direction], j + dc[direction]
                    if in_range(newr, newc) and ori_map[newr][newc] == 2:
                        people_map[newr][newc] =2
                        dfs(newr, newc, length+1, index)
                        break
                # (3) dfs 끝나면, 다음 team 찾아서
                index += 1  # 한 탐색이 끝나면, index +1
def move_one(index):
    """
    팀원 한 칸씩 이동 - 아래 두개 업데이트
    [1] team_list
    [2] people_map
    :param team_index:
    :return:
    """
    global team_list, people_map
    # [1] team_list
    temp = copy.deepcopy(team_list[index])
    team_list[index] = [temp[-1]] + temp[:-1]
    # [2] people_map
    for i, (r,c)  in enumerate(team_list[index]):
        if i+1 <= team_len[index]:
            # 사람 범위 내에 있을 때는 숫자로
            people_map[r][c] =i+1
        else:
            people_map[r][c] = 0

def where_ball(round):
    """
    공이 어느 방향, 몇번째에서 오는지
    :param round: 몇번째 round
    :return: 방향 (0~3), 몇번째(0~n-1)
    """
    ith = round%n
    direction = (round//n)%4
    return direction, ith
def reverse_people(index):
    """
    [1] list 반대
    [2] map 반대 (list를 기반으로)
    :param index:
    :return:
    """
    global team_list, people_map
    # [1]
    temp = copy.deepcopy(team_list[index])
    length = team_len[index]
    team_list[index][:length] = reversed(temp[:length])
    team_list[index][length:] =reversed(temp[length:])

    # [2] people_map
    for i, (r,c)  in enumerate(team_list[index]):
        if i+1 <= length:
            # 사람 범위 내에 있을 때는 숫자로
            people_map[r][c] =i+1
        else:
            break

def ball_hit_try(ball_dir, ball_index):
    """
    공 던져서 맞으면, 처리
    :param ball_dir:
    :param ball_index:
    :param point:
    :return: point
    """
    if ball_dir==0:
        # 좌 -> 우 (최소 column)
        for j in range(n):
            if people_map[ball_index][j]>0:
                point = people_map[ball_index][j] * people_map[ball_index][j]
                index = team_index_map[ball_index][j]
                reverse_people(index)
                return point

    elif ball_dir==1:
        # 하 -> 상 (최대 row)
        for i in range(n-1,-1, -1):
            if people_map[i][ball_index]>0:
                point = people_map[i][ball_index] * people_map[i][ball_index]
                index = team_index_map[i][ball_index]
                reverse_people(index)

                return point
    elif ball_dir ==2:
        # 우 -> 좌 (최대 column)
        for j in range(n-1,-1,-1):
            if people_map[n-1-ball_index][j]>0:
                point = people_map[n-1-ball_index][j]* people_map[n-1-ball_index][j]
                index = team_index_map[n-1-ball_index][j]
                reverse_people(index)
                return point

    else:
        # 상 -> 하 (최소 row)
        for i in range(n):
            if people_map[i][n-1-ball_index]>0:
                point = people_map[i][n-1-ball_index] * people_map[i][n-1-ball_index]
                index = team_index_map[i][n-1-ball_index]
                reverse_people(index)
                return point
    return 0

# main ---------------------------------------
num_questions = int(input())
for question in range(num_questions):
    # input ------------------------------
    n, m, k = map(int, input().split())
    ori_map = [list(map(int, input().split())) for _ in range(n)]
    # 초기화 ------------------------------
    team_index_map = [[-1] * n for _ in range(n)]  # 각 위치에 team index 표시 (이동선 위치), team index는 은 0,1,2,3...m
    people_map = [[0] * n for _ in range(n)]  # 각 위치에 사람 번호 입력 (team은 index map에서)
    team_list = [[] for _ in range(m)]  # team 별 머리부터 꼬리 순서로 모든 이동선표시, index
    team_len = [0] * m  # 각 index마다 team의 길이 저장
    visited = [[False] * n for _ in range(n)]
    index = 0
    # [1] make team_index_map & team_list & headtail_list -------------
    dfs_cover()
    # [2] Round 시작
    point = 0
    for round in range(k):
        # [2-1] 한칸 움직이기
        for team_index in range(m):
            move_one(team_index)
        # [2-2] 공 공격
        ball_dir, ball_index = where_ball(round)  # 공 어디서 던져질지
        point += ball_hit_try(ball_dir, ball_index)  # 공 던지기 - 맞으면, (1) 점수 + (2) 방향 바꾸기

    print(f'#{question+1} {point}')

728x90

'취준! ✒ > 삼성' 카테고리의 다른 글

[코테준비] 삼성21. 코드트리: 정육면체 한번 더 굴리기 python & 삼성식 출력 & 삼성코테 언제부터 4시간? (0)	2023.10.13
[코테준비] 삼성19. 삼성 코테 준비전에 꼭 볼 것- SW Expert에 대해서! (feat. 보호 필름 문제 python) (1)	2023.10.11
[코테준비] 삼성18. 코드트리: 싸움땅 python (1)	2023.10.10
[코테준비] 삼성17. 코드트리: 코드트리 빵 python + 코드트리의 채점 무한로딩 (1)	2023.10.09
[코테준비] 삼성16. 코드트리: 포탑 부수기 python (1)	2023.10.07

취준생 메모장 (AI & CV engineer) 💻

[코테준비] 삼성20. 코드트리: 꼬리잡기놀이 python & 삼성식 출력

꼬리잡기놀이

풀이 노트

정답 코드 (코드트리용)💻

정답 코드 (삼성st)💻

'취준! ✒ > 삼성' 카테고리의 다른 글

티스토리툴바

[코테준비] 삼성20. 코드트리: 꼬리잡기놀이 python & 삼성식 출력

꼬리잡기놀이

풀이 노트

정답 코드 (코드트리용)💻

정답 코드 (삼성st)💻

'취준! ✒ > 삼성' 카테고리의 다른 글

관련글

티스토리툴바