그냥 코딩하는 사람의 블로그

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

풀이 과정

1. 고슴도치와 물의 위치를 저장해 둔다.
2. 단계를 두개로 나누어서 진행한다. 고슴도치가 다음 시간에 물이 찰 예정인 칸으로는 이동할 수 없으므로, 물을 먼저 확산시킨 다음 고슴도치를 이동하는 단계를 거친다.
   1. 물이 퍼지는 단계
   2. 고슴도치가 이동하는 단계
3. BFS 코드를 작성하는데, 고슴도치가 이동하는 횟수를 저장하고, 횟수가 변경될때마다 물을 한번씩 확산시키는 과정을 거친다. 이 때, 물을 확산시키고 나서 확산시킨 위치는 따로 가지고 있어야 다음에 물을 확산시킬 때 위치를 찾을필요 없이 바로 확산시킬 수 있다.
4. 고슴도치가 비버의 굴에 도착하게 되면, 이동시킨 횟수를 출력시켜준다. 도착하지 못하게 되면(큐가 비게되면) KAKTUS를 출력시켜 준다.

소스 코드

import sys
from collections import deque

input = lambda: sys.stdin.readline().rstrip()
R, C = map(int, input().split())
matrix = [list(input()) for _ in range(R)]

water_pos = deque()
visited_biber = set()
biber = deque()
dx = [-1, 1, 0, 0]
dy = [0, 0, 1, -1]

for i in range(R):
    for j in range(C):
        if matrix[i][j] == '*':
            water_pos.append([i, j])
        if matrix[i][j] == 'S':
            visited_biber.add((i, j))
            biber.append([i, j, 0])
            
def flood():
    global R, C, water_pos
    next_deque = deque()
    while water_pos:
        x, y = water_pos.popleft()
        for i in range(4):
            nx, ny = x + dx[i], y + dy[i]
            if 0 <= nx and nx < R and 0 <= ny and ny < C and \
               matrix[nx][ny] not in ['X', 'D', '*']:
                next_deque.append([nx, ny])
                matrix[nx][ny] = '*'
    water_pos = next_deque

step = -1
while biber:
    x, y, current_step = biber.popleft()
    if matrix[x][y] == '*':
        continue
    if matrix[x][y] == 'D':
        print(current_step)
        break
    
    if current_step != step:
        step = current_step
        flood()

    for i in range(4):
        nx, ny = x + dx[i], y + dy[i]
        if 0 <= nx and nx < R and 0 <= ny and ny < C:
            if matrix[nx][ny] != '*' and matrix[nx][ny] != 'X' and \
               (nx, ny) not in visited_biber:
                visited_biber.add((nx, ny))
                biber.append([nx, ny, current_step+1])
else:
    print('KAKTUS')

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

풀이 과정

그냥 풀게 되면 소수점 처리가 조금 난해하므로, 10을 곱해주어 정수로 풀이하는게 더 좋음.

1. 파이프를 오름차순으로 정렬한다.
2. 맨 왼쪽 파이프부터 순차적으로 파이프에 테이프를 붙인다.
   1. 현재 파이프 위치 - 5~ 현재 파이프 위치 + 5에 테이프가 붙어져있는지 확인
      • 확인할 때, set에 해당 위치가 있는지 확인하는 방식으로 진행
   2. 전체가 붙어져있다면 다음 파이프 위치로 넘어간다.
   3. 전체가 붙여져있지 않다면 안붙여진 부분중 가장 왼쪽 위치에다가 테이프를 붙여주어야 한다.
      • 테이프를 붙여줄 때, 붙이는 위치~붙이는 위치 + 10 * L를 Set에 넣어준다.
      • 테이프를 붙인 다음, 테이프 카운트를 하나 늘려준다.
3. 붙인 테이프 개수를 출력한다.

소스 코드

import sys

input = lambda: sys.stdin.readline().rstrip()
N, L = map(int, input().split())

water = list(map(lambda x:int(x)*10, input().split()))
water.sort()
tape = set()
tape_count = 0
for pos in water:
    start = 0
    for i in range(-5, 6):
        if pos+i not in tape:
            start = pos+i
            break
    else:
        continue

    for p in range(start, start+(10*L)+1):
        tape.add(p)
    tape_count += 1

print(tape_count)

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

풀이 과정

1. 최소히프, 최대히프를 만들어 두고, 실제 데이터 개수를 체크할 딕셔너리를 하나 만들어 둔다.
2. 데이터 삽입
   1. 데이터를 최소히프, 최대히프에 모두 삽입
   2. 딕셔너리 내 해당 데이터 개수를 1개 증가시켜 준다.
3. 데이터 삭제
   1. 최소값을 뽑아야 하면 최소히프에서 빼준다.
   2. 최댓값을 뽑아야 하면 최대히프에서 빼준다.
   3. 단, (1), (2) 과정에서 뽑은 데이터에 대응되는 데이터 개수가 0개인 경우에는 이미 다른 히프에서 빼준 것이므로, 다시 빼주어야 한다.
4. 마지막에 큐가 비어있다면 Empty를, 비어있지 않다면 최댓값, 최솟값을 출력한다.
   
   1. 각각 최대히프, 최소히프에서 빼주고, 만약 빼줄 데이터가 없는 경우에는 Empty를 출력시켜주면 된다.

소스 코드

import heapq
import sys
from collections import defaultdict

input = lambda: sys.stdin.readline().rstrip()

T = int(input())
for _ in range(T): 
    min_heap = []
    max_heap = []
    element_dict = defaultdict(lambda: 0)
    K = int(input())
    for __ in range(K):
        cmd, data = input().split()
        data = int(data)
        if cmd == 'I':
            heapq.heappush(min_heap, data)
            heapq.heappush(max_heap, -data)
            element_dict[data] += 1
        if cmd == 'D':
            if data == -1:
                while min_heap:
                    r = heapq.heappop(min_heap)
                    if element_dict[r] > 0:
                        element_dict[r] -= 1
                        break
            else:
                while max_heap:
                    r = heapq.heappop(max_heap)
                    r = -r
                    if element_dict[r] > 0:
                        element_dict[r] -= 1
                        break
    min_value = None
    max_value = None
    while min_heap:
        r = heapq.heappop(min_heap)
        if element_dict[r] > 0:
            min_value = r
            break
            
    while max_heap:
        r = heapq.heappop(max_heap)
        r = -r
        if element_dict[r] > 0:
            max_value = r
            break
    if min_value == None:
        print('EMPTY')
    else:
        print(max_value, min_value)

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

풀이 과정

1. 그냥 진행하면 가방도 최대 30만개고, 보석도 최대 30만개이므로 시간초과가 나타나므로 최대 히프로 풀이한다.
2. 우선 보석을 무게 순으로 최소 히프에 넣어주고, 가방은 오름차순으로 정렬시켜 준다.
3. 가장 가벼운 가방에서부터 순차적으로 루프를 돈다.
   1. 현재 가방에 넣을 수 있는 보석들을 최소 히프에서 하나씩 꺼내면서 보석의 가격 순으로 최대 히프에 넣어준다.
   2. 넣어주는 작업이 끝나면, 최대 히프에서 값을 하나 꺼내서 더해준다. 가벼운 가방에서 무거운 가방 순서로 진행하므로 다음 가방에는 무조건 넣을 수 있는 보석이기 때문에 무게는 같이 저장할 필요가 없음. 최대 히프에서 꺼낸 값이 현재 가방에 넣어줄 보석의 가격이다.
4. 보석 가격의 합을 출력시켜 준다.

소스 코드

import sys
import heapq

input = lambda: sys.stdin.readline().rstrip()
N, K = map(int, input().split())
jewel = []

for _ in range(N):
    M, V = map(int, input().split())
    heapq.heappush(jewel, [M, V])

backpack = [int(input()) for _ in range(K)]
backpack.sort()

jewel_value_heap = []
answer = 0
for b in backpack:
    # 현재 가방에서 가능한 보석 값들 최대 히프에 넣어줌
    while jewel and jewel[0][0] <= b:
        heapq.heappush(jewel_value_heap, -heapq.heappop(jewel)[1])

    # 최대 히프에서 값 하나 꺼내서 더해줌(현재 가방에 들어갈 보석)
    if jewel_value_heap:
        answer -= (heapq.heappop(jewel_value_heap))

print(answer)

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

풀이 과정

1. 왼쪽 위에서 오른쪽 아래로 진행하면서 오른쪽으로 인접한 사탕, 아래로 인접한 사탕을 바꿔본 다음 가장 긴 연속 부분을 구한다. 구한 다음에는 다시 한번 더 바꿔서 원래 위치로 맞추어 준다.
2. 가장 긴 연속 부분을 구할 때는, 행별, 열별로 따로 i번째 요소와 i-1번째 요소가 같다면 개수를 1 증가시키고, 같지 않다면 개수를 1로 설정한다. 또한 개수를 변경할 때마다 최대 길이를 갱신시켜 준다.
3. (1)-(2)의 결괏값중 최댓값을 구해서 출력시켜 준다.

소스 코드

import sys

input = lambda: sys.stdin.readline().rstrip()
n = int(input())

board = [list(input()) for _ in range(n)]

def get_max_candy(board):
    value = 0
    for i in range(n):
        row_v = 1
        col_v = 1
        for j in range(1, n):
            if board[i][j] == board[i][j-1]:
                row_v += 1
            else:
                row_v = 1

            if board[j][i] == board[j-1][i]:
                col_v += 1
            else:
                col_v = 1
            
            value = max(value, row_v, col_v)

    return value


answer = 0
for i in range(n):
    for j in range(n):
        if i+1 < n:
            board[i][j], board[i+1][j] = board[i+1][j], board[i][j]
            answer = max(answer, get_max_candy(board))
            board[i][j], board[i+1][j] = board[i+1][j], board[i][j]
        if j+1 < n:
            board[i][j], board[i][j+1] = board[i][j+1], board[i][j]
            answer = max(answer, get_max_candy(board))
            board[i][j], board[i][j+1] = board[i][j+1], board[i][j]

print(answer)

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

풀이 과정

1. 가능한 모든 경우의 수 리스트를 만든다.
   • 이 때, 자릿수를 하나하나 떼서 리스트로 만드는게 비교가 훨씬 편하다.
   • [[1, 2, 3], [1, 2, 4], ... ]
2. (1)에서 만든 리스트의 요소들을 하나씩 꺼내서 질문과 비교해 본다.
   1. 현재 요소가 정답이라고 가정한다. ex) [1, 2, 3]
   2. 정답이 [1, 2, 3]일때, 질문에 해당하는 스트라이크와 볼의 개수를 구하고 실제로 답한 스트라이크와 볼의 개수와 비교해 본다.
   3. 다르다면 현재 요소는 정답이 아닌 것이므로 다음 요소를 검사한다. ex) [1, 2, 4]
   4. 모든 질문에 대해 구한 결과와 답한 결과가 같다면, 가능성이 있는 답이므로 정답 카운트를 하나 늘려준다.
3. 정답 카운트를 출력시킨다.

소스 코드

import sys
import heapq


sequence = [(i, j, k)
            for i in range(1, 10)
            for j in range(1, 10)
            for k in range(1, 10)
            if i != j and j != k and i != k]

n = int(sys.stdin.readline().rstrip())
num_list = []
strike_list = []
ball_list = []
for _ in range(n):
    num, strike, ball = map(int, sys.stdin.readline().rstrip().split())
    num_list.append(list(map(int, list(str(num)))))
    strike_list.append(strike)
    ball_list.append(ball)

answer = 0

for x, y, z in sequence:
    for i in range(n):
        strike_count = 0
        ball_count = 0
        # 같은 위치에 값도 같은 경우 strike
        # 다른 위치에 있는 경우는 ball
        if num_list[i][0] == x:
            strike_count += 1
        else:
            if num_list[i][0] == y or num_list[i][0] == z:
                ball_count += 1
                
        if num_list[i][1] == y:
            strike_count += 1
        else:
            if num_list[i][1] == x or num_list[i][1] == z:
                ball_count += 1
                
        if num_list[i][2] == z:
            strike_count += 1
        else:
            if num_list[i][2] == y or num_list[i][2] == x:
                ball_count += 1

        if strike_count != strike_list[i] or ball_count != ball_list[i]:
            break
    else:
        answer += 1

print(answer)

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

풀이 과정

1. 단방향 그래프이므로 시작점을 X를 제외한 모든 점에서 다익스트라 알고리즘을 진행해보아야 한다.
   1. 시작하기 전에, X점에서 다익스트라 알고리즘을 적용하여 X점에서 각각의 점 사이의 최단 경로를 구해준다. 최단 경로 리스트를 X_to_S라고 둔다.
   2. 이후, i점에서 다익스트라 알고리즘을 사용하여 X점까지의 거리를 구한 다음, X점에서 다시 i점으로 돌아가야 하므로 X_to_S[i]를 더해준 다음 정답을 갱신시켜 준다.
2. 다익스트라 알고리즘의 경우 거리가 가장 짧은 노드를 선택할 때 최소 히프를 사용해 주면 조금 더 빠르게 풀이를 할 수 있다.
3. 최종적으로 갱신된 정답을 출력한다.

소스 코드

import sys
import heapq

INT_MAX = int(10e9)

input = lambda: sys.stdin.readline().rstrip()
N, M, X = map(int, input().split())
graph = [[] for _ in range(N+1)]

for _ in range(M):
    s, e, t = map(int, input().split())
    graph[s].append([e, t])

def dijkstra(X):
    heap = []
    time = [INT_MAX] * (N+1)
    time[X], time[0] = 0, 0
    heapq.heappush(heap, [0, X])

    while heap:
        curr_time, city = heapq.heappop(heap)
        if curr_time != time[city]:
            continue
        for e, t in graph[city]:
            if time[e] > t + curr_time:
                time[e] = t + curr_time
                heapq.heappush(heap, [time[e], e])

    return time

X_to_S = dijkstra(X)
answer = 0
for i in range(1, N+1):
    if i == X: continue
    answer = max(answer, dijkstra(i)[X] + X_to_S[i])

print(answer)

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

풀이 과정

1. 현재 아기 상어의 위치를 찾아 두고, 아기 상어의 위치를 조정해주는 방식으로 진행하면 된다.
2. 다음에 사냥할 물고기는 BFS를 통해서 찾아준다.
   1. 단, 이 때 현재 아기 상어의 크기보다 큰 물고기로는 이동 불가능, 크기와 같은 물고기는 이동은 가능하지만 사냥 불가능한 점에 유의해서 BFS 수행
   2. 사냥 가능한 물고기가 등장하게 되면, 이동 길이를 저장해 두고 이동 길이가 같으면서 사냥 가능한 물고기가 또 있는지 찾아본다.
   3. 사냥 가능한 물고기 리스트를 행 기준으로 1차 정렬, 열 기준으로 2차 정렬해 준다. ( 거리는 모두 같으므로 고려할 필요 없이 좌표상 맨 위에 있어야 하며, 같은 행인 경우는 맨 왼쪽에 있어야 하므로 )
   4. 정렬된 물고기 리스트의 첫번째 요소가 사냥할 물고기의 위치이다.
3. 상어의 위치를 사냥할 물고기의 위치로 이동시키고, 이동 거리를 더해준다.
4. 상어의 현재 크기에서 사냥한 물고기의 수가 현재 크기가 된다면 상어의 크기를 하나 올려주고 사냥한 물고기 수를 0으로 초기화시켜 준다.
5. 사냥이 불가능할 때까지 2-4 과정을 반복한다.
6. 누적 이동 거리를 출력시켜 준다.

소스 코드

import sys
from collections import deque


input = lambda: sys.stdin.readline().rstrip()

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

# row, col, level
babyshark = [0, 0, 2]

for i in range(n):
    for j in range(n):
        if matrix[i][j] == 9:
            babyshark[0], babyshark[1] = i, j

def get_next_fish(babyshark):
    global n
    queue = deque([[babyshark[0], babyshark[1], 0]])
    visited = set()
    visited.add((babyshark[0], babyshark[1]))
    dx = [-1, 0, 0, 1]
    dy = [0, -1, 1, 0]

    minimum = int(10e9)
    candidate = []
    while queue:
        x, y, mv = queue.popleft()
        if mv == minimum:
            break
        for i in range(4):
            nx, ny = x + dx[i], y + dy[i]
            if 0 <= nx and nx < n and 0 <= ny and ny < n and \
               (nx, ny) not in visited and \
               matrix[nx][ny] <= babyshark[2]:
                queue.append([nx, ny, mv+1])
                visited.add((nx, ny))
                if matrix[nx][ny] != 0 and matrix[nx][ny] != 9 and \
                   matrix[nx][ny] < babyshark[2]:
                    minimum = mv+1
                    candidate.append([nx, ny])
    if candidate:
        candidate.sort(key=lambda x:(x[0], x[1]))
        return candidate[0][0], candidate[0][1], minimum
    else:
        return -1, -1, minimum
    

    
time = 0
eat_count = 0
while True:
    x, y, dist = get_next_fish(babyshark)
    if x == -1 and y == -1:
        break
    time += dist
    matrix[babyshark[0]][babyshark[1]] = 0
    babyshark[0], babyshark[1] = x, y
    matrix[babyshark[0]][babyshark[1]] = 9
    eat_count += 1
    if eat_count == babyshark[2]:
        babyshark[2] += 1
        eat_count = 0

print(time)

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

풀이 과정

1. 핵심은 격자를 흰칸 격자, 검은칸 격자로 나누어서 보아야 한다는 점
   1. 격자의 크기가 10x10을 통째로 보게 된다면 다 한번씩 둬봐야 하므로 시간초과가 걸리게 된다.
   2. 따라서, 흰 칸에 있는 비숍, 검은 칸에 있는 비숍을 따로 보면 된다. => 5x5 격자를 두번 보는 셈
2. 우선 전체 격자를 스캔하면서 비숍의 위치를 리스트에 넣어준다.
   1. 이 때, x좌표 + y좌표가 짝수라면 흰칸, x좌표 + y좌표가 홀수이면 검은칸 
   2. 비숍의 위치가 검은칸이라면 검은칸 비숍만 저장해두는 리스트에, 흰 칸이라면 흰칸 비숍만 저장해두는 리스트에 따로따로 저장해 둔다.
3. 검은칸일때, 흰칸일때 따로따로 recursion으로 비숍을 하나하나 둬보면서 시뮬레이션 한다.
   1. i번째 비숍을 둘 때, 현재 둔 비숍과 겹치는지(대각선) 확인한다. 
   2. 겹친다면 비숍을 두지 않고 i+1번째 비숍으로 넘억나다.
   3. 겹치지 않는다면 비숍을 두고 i+1번째 비숍으로 넘어가 보고, 비숍을 두지 않을수도 있으므로 두지 않고도 i+1번째 비숍으로 넘어가본다.
4. 검은칸 일때의 최대 비숍의 수, 흰칸 일때의 최대 비숍의 수를 더한 다음 출력한다.

와.. 단순하게 격자를 10x10으로만 보았는데 찾아보니 흰칸, 검은칸을 따로따로 보아야 한다고 함.. 간단하게 소스 몇줄만 바꿔주었을 뿐인데 극적으로 효율이 좋아짐. 10x10에 대해 백트래킹 하는것 보다 5x5에 대해 백트래킹 두번 하는게 훨씬 빠르다는 거에 유의하고 백트래킹을 하려고 할 때 너무 크면 쪼개서 백트래킹 해야된다는걸 배움.

소스 코드

import sys

input = lambda : sys.stdin.readline()

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

bishop = set()
white_bishop_list = [(x, y) for x in range(n) for y in range(n) if matrix[x][y] == 1 and (x+y)%2 == 0]
black_bishop_list = [(x, y) for x in range(n) for y in range(n) if matrix[x][y] == 1 and (x+y)%2 == 1]

save = [0]

def solve(bishoppos, color):
    can_bishop_list = []
    if color == 0:
        can_bishop_list = white_bishop_list
    else:
        can_bishop_list = black_bishop_list
    
    if bishoppos == len(can_bishop_list):
        save[0] = max(save[0], len(bishop))
        return

    current = can_bishop_list[bishoppos]
    can = True
    for x, y in bishop:
        if abs(x-current[0]) == abs(y-current[1]):
            can = False
            break

    if can:
        bishop.add((current[0], current[1]))
        solve(bishoppos+1, color)
        bishop.remove((current[0], current[1]))
    solve(bishoppos+1, color)

answer = 0
# white
solve(0, 0)
answer += save[0]

# black
save[0] = 0
bishop = set()
solve(0, 1)
answer += save[0]

print(answer)

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

풀이 과정

1. 문제 이해하기가 제일 어려웠음. 즉, 계란을 왼쪽에서 오른쪽으로 한번씩 들어야 함. 또한 전체 계란 중에서 깨지지 않은 계란이 있다면 칠 수 있으며, 손에 든 계란이 깨졌거나 더이상 깨뜨릴 계란이 없다면 한 칸 오른쪽 계란을 들면 됨. 여기서 더이상 깨뜨릴 계란이 없다면, 계속 오른쪽으로 이동하여 결국 종료하게 될 것
2. 재귀함수를 구성한다.
   1. 현재 단계가 마지막 단계라면(맨 오른쪽 계란까지 모두 끝난 상태), 전체 계란을 조사하면서 계란이 몇개 깨졌는지 카운팅 해주어야 함.
   2. 현재 손에 든 계란이 깨져있거나 안깨진 계란이 없다면 바로 현재 계란의 다음 계란으로 이동함.
   3. (2)를 통과하게 된다면, 시뮬레이션 해주어야 함. 칠 수 있는 계란을 한번씩 다 쳐보는 과정. 하나의 계란을 쳐본 다음에는 다시 더해서 원래 계란으로 만들어 주고, 다음 계란을 쳐주어야 함.
3. 정답을 출력한다.

소스 코드

import sys

input = lambda : sys.stdin.readline()

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

def solve(current):
    if current == len(eggs):
        count = 0
        for s, w in eggs:
            if s <= 0:
                count += 1
                
        return count
    # 현재 손에 든 계란 깨짐
    if eggs[current][0] <= 0:
        return solve(current+1)

    # 안깨진 계란이 남아있는지 체크하는 부분
    for i in range(len(eggs)):
        if i == current:
            continue
        if eggs[i][0] > 0:
            break
    else:
        return solve(current+1)
            
    # 시뮬레이션
    answer = 0
    for i in range(len(eggs)):
        if i == current:
            continue
        if eggs[i][0] <= 0:
            continue

        eggs[i][0] -= eggs[current][1]
        eggs[current][0] -= eggs[i][1]
        
        answer = max(answer, solve(current+1))

        # 다음 차례 가려면 기존에 빼주었던거 다시 더해주어야 함.
        eggs[i][0] += eggs[current][1]
        eggs[current][0] += eggs[i][1]
    
    return answer

print(solve(0))