Coding 공부

# 2714 로봇 시뮬레이션
# A,B, A은 가로, B는 세로 N은 로봇들
# L,R,F : 로봇기준 왼쪽 90도, 로봇방향 기준 오른쪽 90도, 로봇 기준 앞으로 GO
# 잘못된 명령 : Robot X crashes into the wall: X번 로봇이 벽에 충돌
# Robot X crashes into robot Y : X번 로봇이 Y번 로봇에 부딪힘
def rotate_dire(rotate,current):
    dire_left = [3,0,1,2]
    dire_right = [1,2,3,0]
    if rotate == 'L':
        return dire_left[current]
    else:
        return dire_right[current]


def display_crash(flag,*numbers):
    if flag:
        return f'Robot {numbers[0]} crashes into the wall'
    else:
        return f'Robot {numbers[0]} crashes into robot {numbers[1]}'


A,B = map(int,input().split())
N,M = map(int,input().split())
robots = {}
robot_place = {}
#  E : 0 , S : 1 , W : 2 , N : 3
dire_match = {'E':0,'S':1,'W':2,'N':3}
for robot_number in range(1,N+1):
    X,Y,dire = input().split()
    robots[robot_number]= (int(X),int(Y),dire_match[dire])
    robot_place[(int(X),int(Y))] = robot_number
command_list = []
for _ in range(M):
    robot_number,command,repeat = input().split()
    command_list.append((int(robot_number),command,int(repeat)))

flag = True
result = 'OK'
go_robots = [(1,0),(0,-1),(-1,0),(0,1)]


while command_list:
    command_robot,command,repeat = command_list.pop(0)
    cu_X, cu_Y,cu_dire = robots[command_robot]
    del robot_place[(cu_X,cu_Y)]
    for _ in range(repeat):
        if command == 'F':
            next_X = cu_X + go_robots[cu_dire][0]
            next_Y = cu_Y + go_robots[cu_dire][1]
            if 1<= next_X <= A  and 1<= next_Y <= B:
                if robot_place.get((next_X,next_Y)):
                    flag = False
                    result = display_crash(False,command_robot,robot_place[(next_X,next_Y)])
                    break
                else:
                    cu_X = next_X
                    cu_Y = next_Y

            else:
                flag = False
                result = display_crash(True,command_robot)
                break 
        else:
            cu_dire = rotate_dire(command,cu_dire)

    robots[command_robot] = (cu_X,cu_Y,cu_dire)
    robot_place[(cu_X,cu_Y)] = command_robot
    if not flag:
        break


print(result)

이 문제는 구현,시뮬레이션 문제이고 문제에 주어진 조건대로, 진행시키면 되는 문제이다.

여기서 자주 쓰이는 것들은 함수화, 딕셔너리화 해서 편하게 할 수 있도록 진행했다.

먼저 방향을 숫자로 매핑시켜줬다. 그래야 방향전환시 쉽게 찾을수 있기 때문이다.

그래서 나는 E : 0 , S : 1 , W : 2 , N : 3 으로 각각 매핑시켜두었다. 

이렇게 하고 방향 전환은 rotate_dire라는 함수를 만들어, 오른쪽 왼쪽일때 각각의 리스트를 만들어주고, 방향의 숫자에 맞춰 방향변경시 변경되는 방향을 넣어두었다.

그 다음으로는 이 문제는 2차원 리스트를 통해 구현하는게 일반적인데, 저 같은 경우엔 해당 2차원 리스트에 저장되어있는 정보들이 극히 일부분이고, 무엇보다, 문제에 주어진 행렬은 우리가 일반적으로 만드는 리스트와 상하반전이기때문에, 딕셔너리를 통해 robot들의 정보와 위치정보를 저장시켜주었다.

리스트를 이용해 풀 사람들은 이동방향시 이동하는 위치를 S,N이 바뀌는것만 주의하면 됩니다.

먼저 robots라는 딕셔너리에는 각각의 로봇넘버를 키로 두고 그 안에는 위치정보와 방향정보를 넣어주었다.

그리고 robot_place라는 딕셔너리에는 로봇들의 위치정보를 키로 두고 그 안에 로봇의 넘버를 넣어주었다.

그 다음에는 동서남북을 go_robots 이라는 변수에 저장시켜줬으며, 우리가 위에 매핑시켜놓은 숫자에 맞춰서, 이동을 다음과 같이 [(1,0),(0,-1),(-1,0),(0,1)] 구현해놨다.

이렇게 사전작업을 해둔뒤, 우리가 저장해놓은 command들을 순차적으로 진행시키면 되는 문제이다.

먼저 cu_X,cu_Y,cu_dire 현재의 로봇의 정보를 가져온다. 그리고 난뒤 robot_place에서 해당 위치의 정보를 삭제해준다. 왜냐하면 이동시 robot_place을 기준으로 이동을 탐색하기 때문에, 삭제를 해주는것이다.

그리고 난뒤 명령어가 F일때에는 로봇의 방향으로 전진하는 것이기 때문에, 우리가 만들어놓은 go_robots을 통해 이동시켜주고, 범위가 넘어가지 않는지, 그리고 robot_place에 이미 이동할려는 위치에 로봇이 존재하는지 판단해준다.

그리고 그 결과에 따라, 아무 이상없이 진행되면 cu_X,cu_Y를 next_X,next_Y로 변경시켜준다.

만약 충돌이 발생시에는 발생경우에 따라 다르게 출력될수 있도록 만든 display_crash를 통해 해주는데, 상황에 따라  함수의 input값이 2개가 될수 있으므로, 가변인자를 통해 구현해주었습니다.

명령어가 'L','R'일때에는 rotate_dire라는 함수를 실행시켜 방향을 변경시켜줍니다.

 명령어를 수행 하고 난뒤에는 robots와 robot_place 딕셔너리에 마지막으로 변경된 값들을 저장해주면 됩니다.

모든 명령어를 수행하고 아무 에러가 없을때에는 result의 기본값인 OK가 출력되도록 하고, 아닐시에는 에러 메시지가 출력되도록 구현했습니다.

# 12851 숨바꼭질

N,M = map(int,input().split())
dp = [-1]*100001
if M != N:
    stack = [(N,0,'')]
    flag = False
    result = float('inf')
    dire = ['M','P','T']
    total = set()
    visited = set()
    while stack:
        X,time,how = stack.pop(0)
        if time > result:
            break
        temp =  [X-1,X+1,X*2]
        for ind,k in enumerate(temp):
            if 0<=k<=100000 and time+1<=result:
                if dp[k] == -1 or dp[k] == time+1:
                    dp[k] = time+1
                    stack.append((k,time+1,how+dire[ind]))
                    if k == M:
                        result = time+1
                        total.add(how+dire[ind])

        
    print(result)
    print(len(total))
else:
    print(0)
    print(1)

처음에는 단순히 BFS처럼 풀어주었다.  결과값인 result를 큰 수로 설정해놓고, BFS를 하면, 최초로 변하는 값이 제일 작은 값이 되고, 출력되어야하는 값이 되니, result값보다 작은 time일때만 들어오게 설정해주었다. 그리고, 이 문제에서 처음에 틀렸던 이유 중 하나가, 같은 시간대에 정답에 올 수 있는 경우의 수가 많았다. 그래서 방문표시를 해주는 dp를 최초 방문이거나 아니면 time+1과 같을때, 같은시간대일때만 올 수 있도록 해줬다. 

 또한 전체적인 방법의 수를 찾기 위해, 이동방향을 저장해주는 로직을 추가해줬었다. 그래서 목표값 M에 도착을 하면, total에 추가를 해줘서, 전체 방법의 가지수를 찾아냈다.

하지만 이 방식의 문제점은, 시간이 오래걸린다는 점이다. 매번 BFS를 하는것과 같고, 그럼으로서 시간이 느릴수 밖에 없었다.

welog.tistory.com/61에서 풀었던 이모티콘 문제와 비슷한 방식으로 하면 된다. 문제 : www.acmicpc.net/problem/14226

이와 같은 문제는 BFS이기도 하지만, 각각의 BFS를 하는것보다, 한 타임씩 맞춰서 한꺼번에 하는 편이 시간을 절약하는데 도움이 되는 것 같다.

# 12851 숨바꼭질

N,M = map(int,input().split())
times = 0
ways = 0
prev_vistied = {N : 1}
visited = [True]*100001
if N == M:
    ways = 1
while not ways:
    new_visited = {}
    for number in prev_vistied:
        for new_number in [number-1,number+1,2*number]:
            if 0<= new_number <= 100000 and visited[new_number]:
                if new_number == M:
                    ways += prev_vistied[number]
                else:
                    if new_visited.get(new_number):
                        new_visited[new_number] += prev_vistied[number]
                    else:
                        new_visited[new_number] = prev_vistied[number]
    for visited_number in new_visited:
        visited[visited_number] = False
    prev_vistied = new_visited
    times += 1 

print(times)
print(ways)

개선한 방식은 다음과 같다. 

직전에 방문한 지점 prev_visited를 반복문을 돌리고, 방문하지 않았으면, new_visited에 prev_visited에서 누적된 해당 number에 올 수 있는 방법의 가지수를 더해주면 된다.

한번의 반복문이 끝나고 난뒤에, visited 함수에 방문을 한 것을 표시해주고, prev_visted를 new_visited로 변경시켜주면 된다.

이렇게 하면, 위의 BFS는 각각의 방법 하나하나마다 결과값에 도착할때까지 BFS를 하면서 반복문을 돌려야하지만, 이 방법은 number 단위로 해당 number에 올 수 있는 최소 타임을 이용해 한꺼번에, BFS를 한다는 점이다.

위와 같은 time을 세는 문제 같은 경우엔 일반적인 BFS가 아닌, 한 타임별로 전체를 반복문 돌리는 풀이방식도 생각해봐야겠다.

# 2133 타일 채우기

#  3*N 크기의 벽을 2*1 1*2로 채우는 경우의 수를 구해보자
# N = 1 => 0
# N = 2 => 3
# N = 3 => 0
N= int(input())
dp = [0]*31
dp[2] = 3
if N%2:
    print(0)
else:
    # 점화식
    # Dp(N) = DP(N-2)*3 + (2*Dp(N-4)+2*DP(N-6)+2*DP(2))
    for number in range(4,N+2,2):
        temp = 2
        for k in range(number-4,0,-2):
            temp += dp[k]*2
        temp += dp[number-2]*3
        dp[number] = temp
    print(dp[N])

 이런 류의 문제는 점화식을 찾아내지 못하면 힘든 문제인 것 같다.

직접 그려보고 패턴을 파악해서 점화식을 구해냈다.

1. N이 홀수이면 무조건 0 이다. (다 채울 수 있는 방도가 없기 때문이다.)

2. N이 짝수 일때만 구하면 되는데, 최초 값은 N=2일때 3이다.

3. N이 짝수일때 그려보면 해당 N에서만 발견되는 특정 조합이 2가지가 있다.

   - N= 6일때 다음과 같이 가운데가 가로로 누워있고, 양 끝이 세로로 세워진 케이스가 2개가 있다.

4. F(N)을 N일때 가지수라 한다면, F(N-2)*F(2) 만큼의 가지수가 생성이 된다. 이것은 왼쪽에 전체 크기의 N-2크기를 두고, 오른쪽에 크기가 (3*2) 타일을 뒀을때 생길 수 있는 가지수 이다.

5. 여기서 많이 해맸다. 우리는 기본적으로 왼쪽에 N-2 타일을 두고, 오른쪽에 2인 타일을 뒀다. 오른쪽에 타일을 뒀을때도 염두를 해야한다. 이 때 나올 수 있는것은 각 N마다 특수한 경우로 되는 2가지 일때의 모습에 오른쪽에 나머지 크기의 타일을 뒀을때이다. 

  - N이 8일때, 설명하면 다음 그림과 같다. 그림이 많이 조잡하다. 

  - 우측이 각 N에서 나오는 특수한 경우이고, 빨간색 네모만큼 놓는수 만큼 나올 수 있다.

  - 그러니 첫번째 그림은 F(2)*2 이고, 두번째 그림은 F(4) *2 이다.

위의 특징을 최종적으로 정리하면,

수식을 입력해본게 하도 옛날이라 개판이지만, 대략적으로 N=2일때 제외하고는 다음과 같이 진행해주면 된다.

문제 자체는 점화식인 것을  알았지만, 이에 맞는 점화식을 구하는데 너무 힘들었다. 이와 비슷한 문제를 풀어서 연습을 더 해야할 것 같다.

# 2251 물통
#  A,B,C 
#  앞의 두 물통은 비어 있고, 세번째 물통은 가득 차 있다.
# A 물통이 비어있을때 세번째 물통에 담겨 있을 수 있는 물의 양을 구해내시오.
import collections 
max_Bowl = list(map(int,input().split()))
current_bowl = [0,0,max_Bowl[2]]
visited = [[[False]*(max_Bowl[2]+1) for _ in range(max_Bowl[1]+1)] for _ in range(max_Bowl[0]+1)]
# A,B,C
que = collections.deque()
que.appendleft((0,0,max_Bowl[2]))
result = set()
result.add(max_Bowl[2])
while que:
    cureent_water = que.popleft()
    if visited[cureent_water[0]][cureent_water[1]][cureent_water[2]]:
        continue
    if cureent_water[0] == 0:
        result.add(cureent_water[2])
    visited[cureent_water[0]][cureent_water[1]][cureent_water[2]] = True
    # A->B
    if cureent_water[0]+cureent_water[1] >= max_Bowl[1]:
        que.append((cureent_water[0]+cureent_water[1]-max_Bowl[1],max_Bowl[1],cureent_water[2]))
    else:
        que.append((0,cureent_water[0]+cureent_water[1],cureent_water[2]))
    # A->C
    if cureent_water[0]+cureent_water[2] >= max_Bowl[2]:
        que.append((cureent_water[0]+cureent_water[2]-max_Bowl[2],cureent_water[1],max_Bowl[2]))
    else:
        que.append((0,cureent_water[1],cureent_water[0]+cureent_water[2]))
    # B->C
    if cureent_water[1]+cureent_water[2] >= max_Bowl[2]:
        que.append((cureent_water[0],cureent_water[1]+cureent_water[2]-max_Bowl[2],max_Bowl[2]))
    else:
        que.append((cureent_water[0],0,cureent_water[1]+cureent_water[2]))
    # B->A
    if cureent_water[1]+cureent_water[0] >= max_Bowl[0]:
        que.append((max_Bowl[0],cureent_water[1]+cureent_water[0]-max_Bowl[0],cureent_water[2]))
    else:
        que.append((cureent_water[1]+cureent_water[0],0,cureent_water[2]))
    # C->A
    if cureent_water[2] + cureent_water[0] >= max_Bowl[0]:
        que.append((max_Bowl[0],cureent_water[1],cureent_water[2]+cureent_water[0]-max_Bowl[0]))
    else:
        que.append((cureent_water[2]+cureent_water[0],cureent_water[1],0))
    # C->B
    if cureent_water[2] + cureent_water[1] >= max_Bowl[1]:
        que.append((cureent_water[0],max_Bowl[1],cureent_water[2]+cureent_water[1]-max_Bowl[1]))
    else:
        que.append((cureent_water[0],cureent_water[2]+cureent_water[1],0))

result = sorted(list(result))
print(*result)

처음에 풀때 난잡하다. 똑같이 반복되는것을 계쏙 반복해주었다.

A->B,

A->C

B->C

B->A

C->A

C->B

의 과정을 거쳐주면서 방문하지 않은 경우에만 하는 방식으로 했다.

이렇게 하니 단순반복을 계속해서 쓰면서도 알아보기 힘들었다.

A,B,C = map(int,input().split())
def custom_append(a,b,c):
    global visited,stack,result
    if (a,b,c) not in visited:
        visited.add((a,b,c))
        stack.append((a,b,c))
        if a == 0:
            result.add(c)




def move_bowl(origin,target,target_max):
    if origin+target >= target_max:
        origin = origin+target- target_max
        target = target_max
    else:
        target = origin + target
        origin = 0
    return (origin,target)
visited = set()
visited.add((0,0,C))
stack = [(0,0,C)]
result = set()
result.add(C)

while stack:
    ca,cb,cc = stack.pop()
    if ca:
        # A->B
        na,nb = move_bowl(ca,cb,B)
        custom_append(na,nb,cc)
        # A->C
        na,nc = move_bowl(ca,cc,C)
        custom_append(na,cb,nc)
    if cb:
        # B->C
        nb,nc = move_bowl(cb,cc,C)
        custom_append(ca,nb,nc)
        # B->A
        nb,na = move_bowl(cb,ca,A)
        custom_append(na,nb,cc)
    if cc:
        # C->A
        nc,na = move_bowl(cc,ca,A)
        custom_append(na,cb,nc)
        # C->B
        nc,nb = move_bowl(cc,cb,B)
        custom_append(ca,nb,nc)

result = sorted(list(result))
print(*result)

좀 더 깔끔하게 바뀐 풀이방식이다.

물을 옮기는 과정을 하나의 함수로 만들어주었고, stack에 추가해주고 방문표시를 해주는것도 하나의 함수로 만들어줬다.

이렇게 하니, 본문에는 간단하게 남았고, 불필요한 코드를 반복해서 쓸필요성이 없어졌다.

# 입력 지폐의 금액 T 동전의 가지수 k 각 동전 하나의 금액 pi ni가 주어진다.
# 방법의 수는 2^31 -1 을 초과하지 않는다.



T = int(input())

k = int(input())

money = [list(map(int,input().split())) for _ in range(k)]

money.sort(reverse=True)
dp = (T+1)*[0]

dp[0] = 1
for coin_val,coin_cnt in money:
    for current_money in range(T,1,-1):
        for current_cnt in range(1,coin_cnt+1):
            if current_money - current_cnt*coin_val >= 0:
                dp[current_money] += dp[current_money-current_cnt*coin_val]
print(dp[T])

DP 관련 문제였다. 풀고보니 평범한 배낭과 비슷한 로직이었다. 거기서는 가치를 판단하여, 가치값의 최대를 찾는거였다면, 여기는 방법의 가지수를 찾는 것이라 다르지만, 하나의 dp를 이용해 역으로 진행하면서, 누적시켜주는 것에 있어서 비슷하다고 봤다.

기본적이 원리는 다음과 같다.

동전의 가지수 k개가 주어지면,

첫번째 동전으로 만들 수 있는 모든 동전의 종류를 만들어 본다.

그리고 두번째 동전으로 만들 수 있는 모든 동전의 종류를 만들어서 누적시켜준다.

이렇게 k번을 반복을 해준다.

여기서 주의해야할 점은 아래에서 위로 올라가면, 이전에 만들어진 것 때문에, 원치 않는 결과가 나올 수 있으므로,

주어진 목표 금액인 T에서 -1씩 줄여주면서 다이나믹 프로그래밍을 해준다.

여기서 평범한 배낭과 또 다른 점은, 같은 동전이 여러개 존재하는 것이다.

그래서 동전의 개수 n개만큼 반복을 시켜주면서 진행해야한다.

즉 3원짜리 동전이 5개가 있다하면,

1회차   // 2회차

T - 3*1 ,| (T-1) - 3*1, ....

T - 3*2, |(T-1) - 3*2 ,...

T - 3*3, |(T-1) - 3*3, ...

T- 3*4,  |(T-1) - 3*4 .....

T - 3*5, |(T-1) - 3*5 ....

이렇듯 동전의 개수만큼 진행시켜줘야, 그 동전으로 만들 수 있는 모든 경우를 탐색할 수 있다.

여기서 또 주의해야할 점은 T는 동전의 개수를 조정하는 반복문 밖에 있어야한다.

원래 DP에 약하기도 했지만 비슷한 문제를 풀어본 경험이 있었는데도, 푸는데 시간이 오래걸렸다.

이전에 풀었던 문제들도 다시 공부하여, DP에서 필요한 점화식을 빨리 구하는데 노력해야겠다.

from itertools import combinations
from collections import deque
def bfs(active_virus,total_virus):
    global result,virus_list,N
    virus_cnt = 0
    deactive_virus = virus_list-active_virus
    stack = deque()
    spend_time = [row[:] for row in spend_time_stand]
    for x,y in active_virus:
        stack.append((x,y,0))
        spend_time[x][y] = 0
        virus_cnt += 1
    min_time = -1
    while stack:
        x,y,time = stack.popleft()
        if min_time > result:
            return
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0<=nx<N and 0<=ny<N:
                if spend_time[nx][ny] == -1 and (nx,ny) not in wall_list:
                    if (nx,ny) not in deactive_virus:
                        spend_time[nx][ny] = time+1
                        stack.append((nx,ny,time+1))
                        min_time = spend_time[nx][ny]
                        virus_cnt += 1
                    else:
                        spend_time[nx][ny] = 0
                        stack.append((nx,ny,time+1))
                        

        
    if total_virus == virus_cnt:
        if result >min_time and min_time != -1:
            result = min_time


    



N,M = map(int,input().split())
dx = [-1,1,0,0]
dy = [0,0,1,-1]
arr = [list(map(int,input().split())) for _ in range(N)]
virus_list = set()
wall_list = set()
total_virus = N*N
spend_time_stand = [[-1] *N for _ in range(N)]
for x in range(N):
    for y in range(N):
        if arr[x][y] == 2:
            virus_list.add((x,y))
        elif arr[x][y] == 1:
            wall_list.add((x,y))
            total_virus -= 1

start_virus_list = combinations(virus_list,M)
result = float('inf')
if total_virus-len(virus_list)+M != M:
    for lists in start_virus_list:
        bfs(set(lists),total_virus-len(virus_list)+M)
else:
    result = 0

if result == float('inf'):
    print(-1)
else:
    print(result)

연구소 시리즈 문제 중 3번 문제이다. 여기서는 예외로 해야할 곳이 생각외로 많아서 많이 틀리면서 푼 문제이다.

문제 자체를 이해하자면, 처음부터 있는 바이러스들이 존재한다.

그런데 여기서 M개의 바이러스가 활성화 되고, 나머지 바이러스는 비활성 상태가 된다.

활성 바이러스가 비활성 바이러스 가면 활성화 상태가 된다.

여기서 주의해야할 점은 이 점이다. 처음부터 있는 바이러스는 비활성 상태지만 이미 뿌려진 상태이기 때문에, 비활성->활성이 될뿐이지, 이미 바이러스가 존재하기 때문에, 퍼트리는데 드는 시간에는 포함이 되지 않는다.

그리고 두번째로 주의해야할 점은, 퍼트리는데 드는시간에 들지는 않지만, 비활성간을 활성화시키고 넘어가기 위해선 시간이 누적되는 것이다.

예를 들어 

활성 비활성 비활성 빈칸

이렇게 되어있을시, 

1초 뒤

활성 활성 비활성 빈칸

2초뒤

활성 활성 활성 빈칸

3초뒤

활성 활성 활성 활성

이렇게 3초가 걸리는 걸 알 수 있다. 비활성 바이러스는 이미 존재하던 바이러스이기 때문에 새로 퍼트린 바이러스 시간에는 포함되지 않지만, 이동통로로서는 역할을 하기 위해 시간은 지나가줘야한다.

인제 코드로 돌아가서 기본적인 원리는 연구소 문제들과 동일하다.

전체에 바이러스가 퍼트릴수 있는 최소시간을 구하는 것이고, 구하기 전에 전처리 과정을 해준다.

먼저 벽인 부분은 따로 wall_list로 저장해두고, 전체 바이러스가 생길수 있는 공간 N*N에서 1씩 빼준다.

왜냐하면 벽에는 바이러스가 못살기 때문이다.

또한 virus가 존재하는 경우엔, virus_list라는 set에 저장해두었다.

만약 바이러스가 생길수 있는 공간에서 입력된 바이러스의 값을 뺐을때 0이면, 이미 전부 퍼진거니 0을 출력해주면 된다.

그렇지 않을 경우, 바이러스를 퍼트리는 과정을 해준다. 앞에서 virus_list에서 M개의 combination을 뽑아낸다.

퍼지는 시간이 들어갈 주어진 공간과 같은 크기의 행렬을 만들어준다. 또한, 기본값은 -1로 시간상 존재할수 없는 값으로 초기화 해준다.

파이썬의 집합의 특징을 이용해 전체 virus_list에서 active_list(활성화된 바이러스)를 빼주어서, 비활성된 바이러스의 집합을 따로 만들어준다.

그리고 우리가 만든 spend_time이라는 행렬에 활성화된 바이러스의 위치에 0으로 초기화 시켜주고 stack에 넣어준다.

나머지는 기본적인 bfs랑 동일하다.

여기서 주의해야할 점은 deactive_virus인 공간과 빈공간에서 차이점을 둔다.

deactive_virus는 stack에 똑같이 time을 +1 해서 추가해주는 대신 spend_time은 0으로 해준다.

하지만 빈공간일때는 spend_time에 현재시간 +1 을 넣어주고, stack에도 동일하게 넣어준다. 그리고 virus_cnt를 늘려준다.

그리고 여기서 min_time을 갱신시켜준다. bfs는 최단경로를 구하는 것이기 때문에, 가장 마지막에 stack에 들어간 값이 모두 퍼트리는데 걸리는 시간이기 때문이다.

또한 시간을 줄여보고자, 우리가 출력하고자하는 결과 result보다 현재 min_time이 높으면 bfs를 중단시켜주었다.

이 문제에서 여러번 시도하면서 틀렸던 점은 위의 주의점 2가지를 빠르게 파악을 못했기 때문이었다. 문제를 제대로 이해하는데, 더 열심히 해야겠다.

이 문제를 풀면서 틀렸습니다. 됬을때 도움이 되는 반례는

5 1

2 1 1 1 1

2 1 1 1 1

2 1 1 1 1

2 1 1 1 1

2 1 1 1 1

answer = 0

4 2

0 1 1 0

2 1 1 2

2 1 1 2

0 1 1 0

answer = 2

더 많은 반례는 www.acmicpc.net/board/view/43303 , www.acmicpc.net/board/view/59703 를 참조하면 좋겠습니다.

import sys

T = int(input())

for tc in range(T):
    N = int(input())
    result = 0
    arr = [list(map(int,sys.stdin.readline().split())) for _ in range(N)]
    arr.sort()
    min_value = arr[0][1]
    for ind in range(N):
        if ind == 0:
            result += 1
        else:
            if min_value > arr[ind][1]:
                min_value = arr[ind][1]
                result += 1
    print(result)

처음에 입력 받은 그 상태로 서류점수 자체로 sort를 해줬다. 그러면  1번 지원자를 제외한 나머지 지원자들은 이미 서류점수에서, 자기보다 잘 본 사람이 있는 것이다. 

그렇기 때문에 면접점수에서 앞의 사람보다. 순위가 높으면, 두 분야에서 자기보다 잘 본 사람이 있는 것이기 때문에, 최종 탈락하는 것이다.

그래서, 제일 첫번째 지원자의 면접점수를 최소값으로 해주고, 이 값보다 좋은 순위가 있으면 교체를 해주면서 최종합격자 수를 늘려주면 된다.

하지만 이렇게 할시 무조건 처음에 sort를 해야하기 때문에 5000ms 이상의 시간이 걸린다.

import sys

T = int(input())

for tc in range(T):
    N = int(input())
    result = 1
    arr = [0]*(N+1)
    for _ in range(N):
        x,y = map(int,sys.stdin.readline().split())
        arr[x] = y
    min_value = arr[1]
    for ind in range(2,N+1):
        if min_value > arr[ind]:
            min_value = arr[ind]
            result += 1
    print(result)

개선한 방안은 어차피 중복되는 수는 없고 1~N 까지의 순위는 무조건 있기 때문에, 길이가 (N+1)인 1차원 리스트를 만들어주고, index가 서류점수 value가 면접점수가 되도록 한다.

그리고 그 다음은 위와 똑같이 진행해주면 된다.

sort를 진행하지 않기 때문에 실행시간이 확연히 줄어드게 된다.

# 이모티콘 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을 판별하는 과정을 추가하는 순간 시간차이가 확 나는걸 알 수 있다.