18352 특정거리의 도시찾기

• bfs알고리즘을 익히면 크게 어려운 문제는 아닌 것 같다
• bfs를 통해 start부터 모든 도시를 접근해 가며
  거리를 누적시켜 준다
• 거리 리스트에서 k랑 같은게 있으면 출력

import sys
from collections import deque
input = sys.stdin.readline

N, M, K, X = map(int, input().split())
navi = [ [] for _ in range(N) ]
visit = [ 0 for _ in range(N) ]
dist = [ 0 for _ in range(N) ]
cnt = 0

for _ in range(M):
    A, B = map(int, input().split())
    navi[A-1].append(B-1)
    
def bfs(start):
    global cnt
    
    deq = deque([start])
    visit[start] = 1
    
    while deq:
        v = deq.popleft()

        for i in navi[v]:
            if visit[i] == 0 :
                visit[i] = 1
                dist[i] = dist[v]+1
                deq.append(i)

bfs(X-1)
if K not in dist:
    print(-1)
else:
    # 오름차순대로 출력
    for i in range(N):
        if dist[i] == K:
            print(i+1)

18405 경쟁적 전염

• 한시간 반 정도 동안 헤맸는데 안풀어짐
• 한숨 자고 일어나서 풀었더니 쑥쑥 풀어짐
• ㅠㅠ

알고리즘

• 원래 bfs를 사용할 때 queue 구조를 사용한다.
• 하지만 이 문제는 바이러스 종류에 맞게 전염시켜야 하므로 바이러스 종류 수(K) 만큼 2차원 데크를 선언하여 해결하였다 (이거 땜에 헤맸다)
• 받은 입력값에서 0이 아닌(바이러스) 좌표를 2차원 데크에 넣는다
• deq[바이러스 종류-1].append((좌표))

from collections import deque
import sys
input = sys.stdin.readline

#입력값 받기
N, K = map(int, input().split())
board = [ 0 for _ in range(N) ]
for _ in range(N):
    board[_] = list(map(int, input().split()))
S, X, Y = map(int, input().split())
deq = deque([deque() for _ in range(K)] )

#상하좌우
move = [(0,1),(0,-1),(-1,0),(1,0)] 

#받은 입력값에서 0이 아닌(바이러스) 좌표를 2차원 데크에 넣는다
#deq[바이러스 종류-1].append((좌표))
for y in range(N):
    for x in range(N):
        if board[y][x] != 0:
            deq[board[y][x]-1].append((x,y))

def bfs(K,S,X,Y):
    sec = 0
    while deq:
        if sec >= S:
            print(board[Y][X])
            break
        
        for d in range(K):
            for i in range(len(deq[d])):
                x,y = deq[d].popleft()
                
                for tmp_x, tmp_y in move:
                    #범위를 벗어날 시 continue
                    if not(x+tmp_x >= 0 and x+tmp_x < N and y+tmp_y >= 0 and y+tmp_y < N) :
                        continue
                    if board[y+tmp_y][x+tmp_x] == 0:
                        deq[d].append((x+tmp_x,y+tmp_y))
                        board[y+tmp_y][x+tmp_x] = board[y][x]
                    
        sec += 1
                    
bfs(K,S,Y-1,X-1)

14888 연산자 끼워넣기

• 재귀 함수를 통해 연산자 개수 만큼 op_cal()을 반복하여 호출한다
• 최대값과 최소 값을 갱신해주며 최종 최대, 최소 값을 출력한다

import sys
import copy
input = sys.stdin.readline

N = int(input())
num_list = list(map(int, input().split()))
op_list = list(map(int, input().split()))
max_num, min_num = -10e10, 10e10

def check(copied_op,cur):
    global max_num, min_num
    if sum(copied_op) == 0:
        max_num = max(max_num, cur)
        min_num = min(min_num, cur)


def op_cal(idx, opcode_list, cur):
    global max_num, min_num
    
    
    if opcode_list[0] != 0:
        copied_op = copy.deepcopy(opcode_list)
        copied_op[0] -= 1
        tmp_cur = cur+num_list[idx]
        op_cal(idx+1,copied_op,tmp_cur)
        check(copied_op,tmp_cur)
        
    if opcode_list[1] != 0:
        copied_op = copy.deepcopy(opcode_list)
        copied_op[1] -= 1
        tmp_cur = cur-num_list[idx]
        op_cal(idx+1,copied_op,tmp_cur)
        check(copied_op,tmp_cur)

    if opcode_list[2] != 0:
        copied_op = copy.deepcopy(opcode_list)
        copied_op[2] -= 1
        tmp_cur = cur*num_list[idx]
        op_cal(idx+1,copied_op,tmp_cur)
        check(copied_op,tmp_cur)

    if opcode_list[3] != 0:
        copied_op = copy.deepcopy(opcode_list)
        copied_op[3] -= 1
        if cur < 0:
            cur = abs(cur)
            tmp_cur = -1*(cur//num_list[idx])
        else:
            tmp_cur = cur//num_list[idx]
        op_cal(idx+1,copied_op,tmp_cur)
        check(copied_op,tmp_cur)

    return

op_cal(1,op_list,num_list[0])
print(max_num)
print(min_num)

• 다른 사람에 비해 메모리와 시간이 오래 걸렸다
• 아래는 다른 사람 코드..

import sys
input = sys.stdin.readline

n = int(input())
# 연산을 수행하고자 하는 수 리스트
data = list(map(int, input().split()))
# 더하기, 빼기, 곱하기, 나누기 연산자 개수
add, sub, mul, div = map(int, input().split())

# 최솟값과 최댓값 초기화
min_value = 1e9
max_value = -1e9

# 깊이 우선 탐색 (DFS) 메서드
def dfs(i, now):
    global min_value, max_value, add, sub, mul, div
    # 모든 연산자를 다 사용한 경우, 최솟값과 최댓값 업데이트
    if i == n:
        min_value = min(min_value, now)
        max_value = max(max_value, now)
    else:
        # 각 연산자에 대하여 재귀적으로 수행
        if add > 0:
            add -= 1
            dfs(i + 1, now + data[i])
            add += 1
        if sub > 0:
            sub -= 1
            dfs(i + 1, now - data[i])
            sub += 1
        if mul > 0:
            mul -= 1
            dfs(i + 1, now * data[i])
            mul += 1
        if div > 0:
            div -= 1
            dfs(i + 1, int(now / data[i])) # 나눌 때는 나머지를 제거
            div += 1

# DFS 메서드 호출
dfs(1, data[0])

# 최댓값과 최솟값 차례대로 출력
print(max_value)
print(min_value)