Coding 공부

# 이모티콘 S
# 모두복사
# 클립보드 모두 붙이기
def bfs():
    global S
    stack = [(1,0,0)]

    visited = []
    while stack:
        emo_cnt,clip_cnt,second = stack.pop(0)
        if (emo_cnt,clip_cnt) in visited:
           continue 
        visited.append((emo_cnt,clip_cnt))
        if emo_cnt == S:
            break
        stack.append((emo_cnt,emo_cnt,second+1))
        if emo_cnt and clip_cnt:
            stack.append((emo_cnt+clip_cnt,clip_cnt,second+1))
        if emo_cnt > 2:
            stack.append((emo_cnt-1,clip_cnt,second+1))

    return second


S = int(input())


print(bfs())

기본적으로 bfs를 이용해서 풀었다.

bfs를 이용해서 각 단계마다, 추가가 될 수 있으면 추가를 해주는 방식으로 했다.

하지만 List에서 in을 써서 찾는 방식은 시간복잡도가 커서 오래걸려서 다른 방법으로 한번 더 풀었다.

S = int(input())

Set_emo_clip = set()
Set_emo_clip.add((1,0))
flag = False
time = 0
while True:
    time += 1
    temp_set = set()
    for emo_cnt,clip_cnt in Set_emo_clip:
        if (emo_cnt,emo_cnt) not in Set_emo_clip:
            temp_set.add((emo_cnt,emo_cnt))
        if (emo_cnt+clip_cnt,clip_cnt) not in Set_emo_clip:
            temp_set.add((emo_cnt+clip_cnt,clip_cnt))
            if emo_cnt+clip_cnt == S:
                flag = True
                break
        if emo_cnt > 0 and (emo_cnt-1,clip_cnt) not in Set_emo_clip:
            temp_set.add((emo_cnt-1,clip_cnt))
            if emo_cnt-1 == S:
                flag = True
                break
    if flag:
        break
    Set_emo_clip = Set_emo_clip | temp_set
print(time)

set가 dictionary는 List보다 해당 값이 존재하는지 판별하는데 시간이 더 적게 걸리므로, set과 dictionay형태를 쓰거나,

현재 이모티콘의 개수와 클립보드의 개수를 가지고 방문여부를 판단하니, 적당히 큰 2차원배열를 만들어, 방문여부를 체크하는 것도 한 방식일 것 같다.

set, list not in 비교

import time

list_time = time.time()
a = []

for k in range(100000):
    a.append(k)
    if k not in a:
        pass
print(f'list 추가 및 in 판단 시간 : {time.time()-list_time}')

set_time = time.time()

b = set()

for k in range(100000):
    b.add(k)
    if k not in b:
        pass

print(f'set 추가 및 in 확인 시간 : {time.time()-set_time}')

좀 부정확하겠지만, not in을 판별하는 과정을 추가하는 순간 시간차이가 확 나는걸 알 수 있다.

# # # 9019 DSLR 
# # # 레지스터 0이상 10000미만 십진수 저장
# # # n = ((d1 × 10 + d2) × 10 + d3) × 10 + d4
# # # D는 n을 두배로 바꾼다. 결과값이 9999보다 큰 경우는 1만으로 나눈 값 (2n mod 10000)
# # # S : n에서 1을 뺀값 n이 0이면 9999로 대신 저장
# # # L : n을 각자리숫를 왼편으로 회전시켜 그 결과를 레지스터에 저장한다.  d2, d3, d4, d1
# # # R : n을 오른쪽으로 회전 
import collections

def DSLR(num):
    D_num = num *2
    if D_num > 9999:
        D_num = D_num%10000
    S_num = num -1
    if not num:
        S_num = 9999
    L_num = (num*10)%10000 + num//1000
    R_num = num//10 + num%10*1000
    return [D_num,S_num,L_num,R_num]



T = int(input())
DSLR_IND = ['D','S','L','R']
for tc in range(T):
    A,B = list(map(int,input().split()))
    deque = collections.deque()
    deque.append((A,''))
    dp = [0]*10000
    dp[A] = 1
    flag = False
    while deque:
        num,result = deque.popleft()
        if num == B:
            break
        temp = DSLR(num)
        for ind in range(4):
            if not dp[temp[ind]]:
                dp[temp[ind]] = 1
                if temp[ind] == B:
                    result = result + DSLR_IND[ind]
                    flag = True
                    break
                deque.append((temp[ind],result+DSLR_IND[ind]))
        if flag:
            break
    print(result)

이 문제에서 어려웠던 점은 2가지였다.

첫번째는 시간초과의 압박이다. 스트링과 list의 특성을 이용해 L,R을 쉽게 구현을 할려고 했는데, str과 list를 이용해 L,R을 구현하는 순간 시간초과가 계속됬다.

두번째는 L,R의 제대로 된 이해였다.

문제를 처음봤을때 12가 있으면 이게 L이면 21이 되고 R이면 21이 되는줄 알았다. 이렇게 구현을 해놨었는데, 계속 틀렸습니다가 나와서 문제를 찬찬히 읽어보니 이 문제에서는 무조건 4자리로 강제가 되던것이다.

12가 그냥 12가 아닌 0012인 상태인것이다. 그래서 L을 하면 0120이 되는것이고 R을 하면 2001인 것이다. 이부분을 조심해줘서 풀면 되는 것이었다.

이 문제는 modular를 이용해 L,R을 구현해주면 된다.

L은 원래 Number에서 10배를 해주고 10000으로 나머지를 구한뒤, 제일 첫번째 숫자의 몫을 구하기 위해 Number의 1000으로 나눈 몫을 더해주면 된다.

R은 원래 Number를 10으로 나눈 몫을 구하고, 나머지에는 1000을 곱해서 더해주면 된다.

그리고 bfs를 이용해서 풀때, 목표값인 B와 비교를 해주는 것을 for문 밖 popleft를 한 바로 뒤에 나뒀더니, 의미없는 반복문이 더 진행이 되었기 때문에, for문 안에 두어서 바로바로 비교한뒤 flag를 두어서, 바로 결과가 출력되게 만들어줬다.

#  17086 아기 상어
import collections
dx = [-1,0,1,-1,1,-1,0,1]
dy = [-1,-1,-1,0,0,1,1,1]

def bfs(x,y):
    deque = collections.deque()
    deque.append((x,y,0))
    visited = [[True]*M for _ in range(N)]
    visited[x][y] = True
    while deque:
        x,y,cnt = deque.popleft()
        if arr[x][y]:
            return cnt
        for i in range(8):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0<= nx <N and 0<=ny <M:
                if visited[nx][ny]:
                    deque.append((nx,ny,cnt+1))
                    visited[nx][ny] = False


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


arr = [list(map(int,input().split())) for _ in range(N)]
result = 0
for x in range(N):
    for y in range(M):
        if not arr[x][y]:
            temp = bfs(x,y)
            result = max(temp,result)

print(result)

처음에는 각 점에서 BFS를 해서 상어와의 위치값이 가장 먼 값을 구하는 방법을 했다.

import collections
dx = [-1,0,1,-1,1,-1,0,1]
dy = [-1,-1,-1,0,0,1,1,1]
N,M = map(int,input().split())

arr = [list(map(int,input().split())) for _ in range(N)]
shark = collections.deque()
for i in range(N):
    for j in range(M):
        if arr[i][j] == 1:
            shark.append((i,j,arr[i][j]))

while shark:
    x,y,dis = shark.popleft()
    for i in range(8):
        nx = x + dx[i]
        ny = y + dy[i]
        if 0<= nx <N and 0<=ny<M:
            if not arr[nx][ny]:
                arr[nx][ny] = 1
                shark.append((nx,ny,dis+1))


print(dis-1)

 두번째 풀이는 그 반대로, 상어를 기준으로 bfs를 진행했다. 어차피 bfs는 거리순으로 진행되기 때문에, 가장 마지막에 나오는 dis가 최대 거리이므로, 마지막 dis에서 1을 빼줬다.

import collections
dx=[1,-1,0,0]
dy=[0,0,1,-1]
def bfs(n):
    que=collections.deque()
    que.append(n)
    while que:
        t=que.popleft()
        ax=t//1000000
        ay=t%1000000
        visit[ax][ay]=0
        for i in range(4):
            nx=ax+dx[i]
            ny=ay+dy[i]
            if 0<=nx<M and 0<=ny<N:
                if arr[nx][ny]==1 and visit[nx][ny]==-1:
                    que.append(1000000*nx+ny)
                    visit[nx][ny]=0
    return


T=int(input())

for tc in range(1,T+1):
    N,M,K=list(map(int,input().split()))
    arr=[[0 for j in range(N)] for i in range(M)]
    visit=[[-1]*N for i in range(M)]
    
    for _ in range(K):
        y,x=list(map(int,input().split()))
        arr[x][y]=1
    cnt=0
    for i in range(M):
        for j in range(N):
            if arr[i][j]==1 and visit[i][j]==-1:
                cnt+=1
                bfs(i*1000000+j)
    print(cnt)
    

위의 방식은 BFS를 이용해서 푼 방식이다.

dx=[1,-1,0,0]
dy=[0,0,1,-1]
import sys
sys.setrecursionlimit(10**6)
def dfs(x,y,_cnt):
    dist[x][y]=_cnt

    for k in range(4):
        nx=x+dx[k]
        ny=y+dy[k]
        if 0<=nx<N and 0<=ny<M:
            if arr[nx][ny] and dist[nx][ny]==-1:
                dfs(nx,ny,_cnt)




t=int(input())
for _ in range(t):
    M,N,K=map(int,input().split())
    arr=[[0 for col in range(M)] for row in range(N)]
    dist=[[-1 for col in range(M)] for row in range(N)]
    for _ in range(K):
        y,x=map(int,input().split())
        arr[x][y]=1
    
    cnt=0

    for i in range(N):
        for j in range(M):
            if arr[i][j]==1 and dist[i][j]==-1:
                cnt+=1
                dfs(i,j,cnt)
    print(cnt)

    

DFS를 이용한 방식이다.

BFS나 DFS로 풀면 되는 문제이다. 방문한적이 없고 서로 연결된 것들의 개수를 구하면 되는 문제이다.

# 5014 스타트링크
# F층 건물 스타트링크 있는 위치 G 강호가있는 층은 S
# U,D
import collections
def bfs(start,end,up,down):
    global F
    visited[start] = 1
    deque = collections.deque()
    deque.append((start,0))
    dx = [up,-down]
    result = 'use the stairs'
    while deque:
        num,cnt = deque.popleft()
        if num == end:
            result = cnt
            break
        for i in range(2):
            nx = num + dx[i]
            if 0 <= nx <= F:
                if not visited[nx]:
                    visited[nx] = 1
                    deque.append((nx,cnt+1))
    return result


F,S,G,U,D = map(int,input().split())
visited = [0]*(F+1)
visited[0] = 1

print(bfs(S,G,U,D))

기본 원리는 BFS를 이용해서, 최단 이동거리를 이용하는거와 같다. 가장 가까이 갈수 있는 경우를 구하는 것이므로 BFS를 썼다.

여기서 주의해야할 점은 F+1 크기만큼의 viisted의 함수를 만들어주고, deque가 전부 비면, 갈수 있는 방안이 없는걸로 판단해야한다.

import itertools
import collections

def bfs(arr,team):
    q=collections.deque()
    q.append(arr)
    cnt=1
    visited[arr]=True
    while q:
        node=q.popleft()
        for k in graph[node]:
            if visited[k]==False and k in team:
                visited[k]=True
                q.append(k)
                cnt+=1
    if cnt==len(team):
        return True
    else:
        return False
 

N=int(input())
arr=list(range(1,N+1))
people=[0]

people.extend(list(map(int,input().split())))
graph=[[]]
people_total=sum(people)
for i in range(N):
    temp=list(map(int,input().split()))
    graph.append(temp[1:])
min_number=999999999999999
for i in range(1,N//2+1):
    b=itertools.combinations(arr,i)
    for k in b:
        a_team=list(k)
        b_team=list(set(arr)-set(k))
        
        visited=[False]*(N+1)
        
        if bfs(a_team[0],a_team) and bfs(b_team[0],b_team):        
            a_team_sum=0
            for tt in a_team:
                a_team_sum+=people[tt]
            b_team_sum=people_total-a_team_sum
            if abs(b_team_sum-a_team_sum)<=min_number:
                min_number=abs(b_team_sum-a_team_sum)       
    if min_number==0:
        break
if min_number>1000:
    print(-1)
else:
    print(min_number)

기본적인 그래프 이론이다.

기본 컨셉은 combination을 이용해 전체 N에서 절반만큼만 구한다. 이유는 조합은 n-k 와 k일떄의 조합은 같기 때문이다.

그렇게 구한 조합에서 set을 이용해서 서로 뺄샘으로 a_team과 b_team을 구하고, 경로탐색을 통해 서로 이어진 숫자와 팀의 길이와 같은지 구분을 하고, 게리멘더링이 성립되는경우에 두 팀간의 격차를 구하고, 최소값을 갱신해준다.

def bfs(x,y,color):
    global puyo,visited,arr
    temp = [[x,y]]
    stack = [[x,y]]
    while stack:
        sx,sy = stack.pop(0)
        for i in range(4):
            nx = sx + dx[i]
            ny = sy + dy[i]
            if 0<= nx < 12 and 0 <= ny <6:
                if arr[nx][ny] == color and visited[nx][ny]:
                    visited[nx][ny] = 0
                    stack.append([nx,ny])
                    temp.append([nx,ny])
    if len(temp) >= 4:
        return temp
    else:
        return []




arr = [list(input()) for _ in range(12)]
times = 0
dx = [-1,1,0,0]
dy = [0,0,-1,1]
while True:
    visited= [[1]*6 for _ in range(12)]
    puyo = []
    for x in range(12):
        for y in range(6):
            if arr[x][y] != '.' and visited[x][y]:
                visited[x][y] = 0
                check = bfs(x,y,arr[x][y])
                if check:
                    for x,y in check:
                        puyo.append((x,y))
    for x,y in puyo:
        arr[x][y] = '.'
    if len(puyo) == 0:
        break
    new_arr = [['.']*6 for _ in range(12)]
    for y in range(6):
        temp = []
        for x in range(11,-1,-1):
            if arr[x][y] != '.':
                temp.append(arr[x][y])
        for i in range(len(temp)):
            new_arr[11-i][y] = temp[i]
    arr = [row[:] for row in new_arr]
    times += 1
print(times)

 이 문제는 한단계씩 BFS를 돌려서 이어진 뿌요를 찾고, 그 뿌요가 하나도 없으면 멈추면 된다.

# R,C 비어있는곳 . 물이 차있는 * 비버의 굴 d 고슴도치S 돌은 X



R,C = map(int,input().split())

arr = [list(input()) for _ in range(R)]
gos = []
end = []
water = []
visited = [[1] * C for _ in range(R)]
for x in range(R):
    for y in range(C):
        if arr[x][y] != '.' and arr[x][y] != 'X':
            if arr[x][y] == 'S':
                gos.append((x,y,0))
                visited[x][y] = 0
            elif arr[x][y] == 'D':
                end.extend((x,y))
            else:
                water.append((x,y))
dx = [-1,1,0,0]
dy = [0,0,-1,1]
flag = False
water_time = - 1
while gos:
    x,y,time = gos.pop(0)
    if x == end[0] and y == end[1]:
        result = time
        flag = True
        break
    if water_time < time:
        new_water = []
        for wx,wy in water:
            for i in range(4):
                wnx = wx + dx[i]
                wny = wy + dy[i]
                if 0<= wnx <R and 0<= wny <C:
                    if arr[wnx][wny] == '.':
                        new_water.append((wnx,wny))
                        arr[wnx][wny] = '*'
        water_time += 1
        water = [row[:] for row in new_water]
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if 0<= nx < R and 0<= ny < C and visited[nx][ny]:
            if arr[nx][ny] == '.' or arr[nx][ny] == 'D':
                visited[nx][ny] = 0
                if nx == end[0] and ny == end[1]:
                    flag = True
                    result = time + 1
                    break
                gos.append((nx,ny,time+1))
    if flag:
        break
if flag:
    print(result)
else:
    print('KAKTUS')

BFS를 이용해서 문제를 푸는데 한가지만 조심해주면 된다. 물은 한번만 차오르고, 같은시간대에 고슴도치는 여러군데에 들릴수도 있으니, 물이 차오르는 특수조건을 주고, 그때에만 물이 번지는걸 유의해주면 된다.