[백준/프로그래머스] 21주차 스터디 (3190 뱀, 15686 치킨 배달 / 60057 문자열 압축)

3190 뱀

📌문제 링크

https://www.acmicpc.net/problem/3190

💡 문제 풀이

뱀 몸이 늘어났다 줄었다 움직였다 어쨌다 하는 과정을 그려도 이해하기 어려워서... 책을 참고했습니다
늘어나는 과정도 1초에 포함되는 줄 알았는데 아니었네요..

1. 지도에 아무것도 없는 곳은 0, 사과가 있는 곳은 1, 뱀이 있는 곳은 2로 표시한다.
2. 동서남북 이동 계산에 필요한 배열을 만들고, 뱀이 회전하고 이동하는 방향을 index로 계산한다.
   (내가 이해가 안 돼서 그림 그려봄..)
   
3. 뱀이 있는 위치를 큐에 넣고, 뱀이 이동할 때 늘어나는 과정을 큐로 계산한다.
   • 꼬리 위치가 큐의 앞에, 머리 위치가 큐의 뒤에 오도록 한다.
   • 뱀이 이동할 때 새롭게 이동한 머리의 위치를 큐에 삽입한다.
   • 이동한 위치에 사과가 없다면 큐의 첫 번째 값(꼬리 위치)를 pop하고, 사과가 없다면 그대로 둔다.

📋코드

# 3190 뱀
import sys
n = int(input())
k = int(input())
# 맵 정보
data = [[0 for _ in range(n + 1)] for _ in range(n + 1)]
# 방향 전환 정보
info = []
# 처음에 오른쪽을 보고 있으므로 (동, 남, 서, 북)
dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]

# 사과가 있는 곳은 1로 표시
for i in range(k):
    a, b = map(int, sys.stdin.readline().split())
    data[a][b] = 1

l = int(input())

for i in range(l):
    x, c = sys.stdin.readline().split()
    info.append((int(x), c))

def turn(direction, c):
    # 왼쪽으로 90도 회전
    if c == "L":
        direction = (direction - 1) % 4
    # 오른쪽으로 90도 회전
    else:
        direction = (direction + 1) % 4
    
    return direction

def simulate():
    x, y = 1, 1 # 뱀의 머리 위치
    data[x][y] = 2 # 뱀이 존재하는 위치는 2로 표시
    direction = 0
    # 처음에는 동쪽을 보고 있음
    time = 0 # 시작한 뒤부터 흐른 시간 (초)
    index = 0 # 다음에 회전할 정보
    q = [(x, y)]

    while True:
        # 이동한 위치 계산
        nextX = x + dx[direction]
        nextY = y + dy[direction]

        # 이동한 위치가 맵 범위 안에 있고, 뱀의 몸통이 없는 위치일 때
        if 1 <= nextX <= n and 1 <= nextY <= n and data[nextX][nextY] != 2:
            # 사과가 없다면 이동 후 꼬리 제거
            if data[nextX][nextY] == 0:
                # 뱀 머리 이동
                data[nextX][nextY] = 2
                q.append((nextX, nextY))
                # 꼬리 제거
                pastX, pastY = q.pop(0)
                data[pastX][pastY] = 0
            # 사과가 있다면 이동 후 꼬리 그대로 둠
            if data[nextX][nextY] == 1:
                data[nextX][nextY] = 2
                q.append((nextX, nextY))
        # 벽이나 몸통에 부딪혔다면
        else:
            time += 1
            break
        
        x, y = nextX, nextY # 뱀의 머리 위치 이동
        time += 1

        # 회전할 시간인 경우
        if index < l and time == info[index][0]:
            direction = turn(direction, info[index][1])
            index += 1
    
    return time

print(simulate())

15686 치킨 배달

📌문제 링크

https://www.acmicpc.net/problem/15686

💡 문제 풀이

처음에 생각한 풀이

1. 치킨집과 집의 위치 정보를 각각의 배열에 저장한다.
2. 모든 집과 치킨집 사이의 거리를 구해서 2차원 배열에 저장한다. (행 : 집, 열 : 치킨)
   -> 치킨 거리는 각 행의 최솟값의 합
3. 현재 치킨집의 개수와 폐업시키지 않을 치킨집의 개수가 같으면 현재 치킨 거리를 출력한다.
4. 폐업시키지 않을 치킨집은 가장 많은 집과 가까이 있는 치킨집 순서로 결정한다. (치킨 거리로 선택이 많이 된 치킨집 순서)
5. 선택된 횟수가 같다면, 치킨집 기준으로 집과의 거리 합이 가장 작은 순서로 결정한다.

이렇게 생각했는데, 너무 복잡하고 시간 효율성도 떨어질 것 같아서 책을 확인해보니 단순히 모든 경우를 일일이 계산해 보는 게 답이었다.
앞으로는 꼭 입력 값의 범위를 확인하고, 범위가 작으면 단순무식하게 풀 수 있다는 것을 기억해야겠다...

책에 나온 풀이

치킨집의 개수 범위는 M <= 치킨 집의 개수 <= 13이다. 치킨집 중에 M개를 선택하는 경우의 수는 13개 중에 M개를 고르는 조합의 수와 같다(13Cm). 이 조합의 값은 100,000을 넘지 않는다.
집의 개수 또한 최대 100개이기 때문에, 모든 경우의 수를 다 계산하더라도 시간 초과 없이 문제를 해결할 수 있다.

파이썬에서는 combinations 라이브러리를 사용하여 간단히 조합을 구할 수 있다!

from itertools import combinations
list(combinations(arr, 2))

이런 식으로 사용하는데, arr라는 리스트에서 2개를 뽑는 모든 조합을 구해 리스트로 변환해준다.

📋코드

# 15686 치킨 배달
import sys
from itertools import combinations

n, m = map(int, sys.stdin.readline().split())
data = []
chicken = [] # 치킨집 위치
home = [] # 집 위치

# 위치 정보 입력
for i in range(n):
    tmp = list(map(int, sys.stdin.readline().split()))
    data.append(tmp)
    for j in range(n):
        if tmp[j] == 2:
            chicken.append((i, j))
        elif tmp[j] == 1:
            home.append((i, j))

# 모든 치킨집 중에서 m개의 치킨집을 뽑는 조합 계산
candidates = list(combinations(chicken, m))

# 치킨 거리의 합을 계산하는 함수
def get_sum(candidates):
    result = 0
    # 모든 집에 대해
    for hx, hy in home:
        # 가장 가까운 치킨집 찾음
        tmp = int(1e9)
        for cx, cy in candidates:
            tmp = min(tmp, abs(hx - cx) + abs(hy - cy))
        # 가장 가까운 치킨집 거리 더함
        result += tmp
    # 치킨 거리 반환
    return result

# 치킨 거리의 합의 최솟값 출력
result = int(1e9)
for candidate in candidates:
    result = min(result, get_sum(candidate))

print(result)

60057 문자열 압축

📌문제 링크

https://programmers.co.kr/learn/courses/30/lessons/60057

💡 문제 풀이

s의 길이는 최대 1000이고, 가장 짧게 압축하는 경우는 문자열을 반토막 내는 것이니 (문자열 2개의 반복으로 이루어진 경우) 모든 경우의 수를 일일이 계산해도 시간 안에 풀 수 있겠다고 생각했다!

(자세한 풀이는 주석에)

📋코드

def solution(s):
    # 문자열의 길이
    length = len(s)
    # 압축이 하나도 되지 않았을 때가 최대 압축 값
    answer = length

    # 문자열을 자를 수 있는 경우의 수는 1개부터 문자열의 절반까지
    for i in range(1, length//2 + 1):
        st = s[0:i] # 처음 시작하는 문자 단위 묶음
        repeat = 1 # 반복 횟수
        tmp = 0 # 압축 길이

        # 두 번째 단위 묶음부터 문자열의 끝까지 압축 단위 길이만큼 건너뛰며 반복
        for j in range(i, length+i, i):
            # 현재 문자 단위 묶음과 다음 문자 단위 묶음이 같을 때
            # 즉, 같은 문자열이 반복될 경우
            if st == s[j:j+i]:
                repeat += 1 # 반복 횟수 증가
            
            # 문자열이 반복되지 않을 경우
            else:
                if repeat == 1: # 한 번 반복할 때는 숫자 생략
                    tmp += len(st)
                # 두 번 이상 반복할 경우 숫자 포함
                else:
                    tmp += len(st) + len(str(repeat))
                
                # 다음 문자열로 이동
                st = s[j:j+i]
                # 반복 횟수 초기화
                repeat = 1

        # 가장 작은 압축 길이 계산
        answer = min(answer, tmp)

    return answer

예상대로 입력 범위가 크지 않아 꽤 짧은 시간 안에 해결할 수 있었다
치킨 배달을 먼저 풀지 않았다면 헤맸을 것 같은데 다행히 잘 풀었다!!