백준 #3190 뱀

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

문제

생각

1. 그래프 탐색 하듯이 풀면 되지 않을까?!
2. 빈공간 0, 사과 1, 뱀을 -1로 해서 구현해보자.
   처음에 문제 세부 사항을 이해하기가 어려워서 직접 그려보며 이해...
   
3. move()함수를 만들어서 뱀의 머리가 도달한 곳에 사과가 있을때, 없을때로 나누어 계속 움직여주면 되겠다!
4. 회전 구현에서 막힘... -> 교재 참고

구현

해당 문제는 처음부터 이동하는 방향이 정해져 있고, 출력에 따라 바뀌는 방향도 정해져있다.
이거를 dy dx 리스트를 이용해 동쪽, 남쪽, 서쪽, 북쪽 순서대로 선언해줌으로써 현재 위치, 입력 받은 알파벳에 따라 그때그때 다른 회전을 구현할 수 있다.

코드

import sys

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

#움직이기
def move ():
    x, y= 0, 0 #머리 위치
    s=0 #초
    board[0][0]=-1 #뱀이 존재하는 위치는 -1로 표시
    direction=0 #현재 방향, 처음에는 동쪾
    q=[(y,x)] #뱀이 차지하고 있는 위치
    index=0
    while True:
        nx=x+dx[direction]
        ny=y+dy[direction]
        if 0<=nx and nx<N and 0<=ny and ny<N and board[ny][nx]!=-1:
            if board[ny][nx]==0: #만약 사과가 없다면
                board[ny][nx]=-1 #머리쪽을 -1로 표시
                q.append((ny,nx)) #머리를 q에 넣음
                py,px=q.pop(0) #꼬리쪽 좌표를 뺀다
                board[py][px]=0 #0으로 바꿔준다
            if board[ny][nx]==1: #사과가 있다면
                board[ny][nx]==-1 #머리쪽을 -1로 표시
                q.append((ny,nx)) #머리를 q에 넣음
        else: #머리가 벽에 닿았거나 뱀의 몸통과 닿았을때
            s+=1 #초 추가후 끝낸다
            break
        x, y = nx,ny #다음 위치로 머리를 이동
        s+=1 #초 추가
        if index<L and s==info[index][0]:
            direction=rotation(direction,info[index][1])
            index+=1

        
    return s   

#입력

N=int(sys.stdin.readline().rstrip())
K=int(sys.stdin.readline().rstrip())
board=[[0]*N for _ in range(N)] #보드 정보
info=[] #방향 회전 정보

#보드 정보 : 사과가 있는 곳은 1
for _ in range(K):
    y,x=map(int, sys.stdin.readline().split())
    board[y-1][x-1]=1
    
L=int(sys.stdin.readline().rstrip())
#방향 회전 정보 : (초,방향)
for _ in range(L):
    x,c=map(str, sys.stdin.readline().split())
    info.append((int(x),c))
    
#순서대로 오른쪽, 아래쪽, 왼쪽, 위쪽
dx=[1,0,-1,0]
dy=[0,1,0,-1] 

print(move())

백준 #15686 치킨 배달

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

문제

생각

도시의 모든 치킨집 중 최대 M개를 고르는 경우의 수 x (M x 집의 개수)
치킨 집 최대 수 13 집 최대수 100
17CN x N x 100
괜찮을 것 같다!

코드

import sys
from itertools import *

n,m=map(int,sys.stdin.readline().split()) #board 크기
board=[list(map(int,sys.stdin.readline().split())) for _ in range(n)]
chicken=[]
home=[]
distance=1e9

#보드를 돌며 치킨집의 좌표와 집의 좌표를 리스트로 저장한다.
for i in range(n):
    for j in range(n):
        if board[i][j]==1:
            home.append((i,j))
        elif board[i][j]==2:
            chicken.append((i,j))
#m개의 치킨집을 고르는 조합의 수
combis=list(combinations(chicken,m))
#모든 조합을 돌면서
for combi in combis:
    d=0
    for hx, hy in home:
        tmp=1e9
        #집 1개당 치킨집 m개까지의 거리를 모두 구한 후 최소값(tmp) 저장 = 치킨 거리
        for cx, cy in combi:
            tmp=min(tmp,abs(hx-cx)+abs(hy-cy))
        #해당 치킨거리를 d에 더해준다
        d+=tmp #도시의 치킨거리
    #모든 조합의 도시의 치킨 거리를 계산해 어느 조합이 치킨거리가 가장 짧은지 구한다.
    distance=min(distance,d)
            
print(distance)

프로그래머스 60057 문자열 압축

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

문제

생각

만약 문자열의 길이가 10이라면 압축할 수 있는 최대 범위는 5
즉, 문자열이 s라고 했을 때 len(s)의 1/2 이다.
가능한 단위마다(1~len(s)/2) 해당 문자열을 압축 시켜 보고,
그 중 가장 작은 것을 출력하면 된다.

코드

def solution(s):
    length=len(s)
    minlen=length
    str1, str2 = "",""
    
    #가능한 단위 범위 만큼 반복
    for unit in range(1,int(length/2)+1):
        tmplen=0 #해당 단위에서의 길이를 저장하는 변수
        num=1 #같은 갯수를 세는 변수
        cur=0 #커서
        while cur<length:
            str1=s[cur:cur+unit]
            str2=s[cur+unit:cur+(2*unit)]
            #str1, str2에 단위만큼 잘라준다
            if str1==str2: 
            #만약 같다면 다음 문자에도 같을 확률이 있으니 num+=1 해준 후 넘어간다. 
                num+=1
            else:
            #다르다면 문자열에 추가 시켜준다
                if num==1: #만약 num=1이라면 => 이전에 같은 문자열이 없어서 압축 시킬 필요가 없다면 
                    tmplen+=len(str1) #해당 문자열(str1)의 길이만 더함
                else: #1보다 크다면 => 이전에 같은 문자열이 있었어서 압축 시켜야 한다.
                    tmplen+=len(str(num)) #num의 자릿수를 고려하기 위해 len(str(num))을 더해준후 
                    tmplen+=len(str1) #해당 문자열(str1)의 길이를 더해준다.
                    num=1       
            cur+=unit
        #작은 길이를 저장    
        minlen=min(minlen,tmplen)

    return minlen