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

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

그냥 풀기 너무 어려워서 백준 내 질문게시판을 참조함..

풀이 과정

1. 출구가 한곳이 아니므로 전체 테두리를 .으로 감싸서 외부에서 시작할 때는 [0, 0]에서 시작할 수 있도록 한다.
2. 총 3번의 BFS를 진행하여야 한다.
   1. 1번 죄수 기준으로 BFS를 진행하여 전체 지점에서 부숴야 하는 최소 벽 개수를 구한다.
   2. 2번 죄수 기준으로 BFS를 진행하여 전체 지점에서 부숴야 하는 최소 벽 개수를 구한다.
   3. 외부 조력자 기준([0, 0])으로 BFS를 진행하여 전체 지점에서 부숴야 하는 최소 벽 개수를 구한다.
3. 전체 좌표에 대해서, 1번 죄수가 부숴야하는 벽, 2번 죄수가 부숴야하는 벽, 외부 조력자가 부숴야 하는 벽의 수를 모두 합한 값이 최소일 때의 값을 출력한다.
   • 단, 이 때 현 좌표가 벽인 경우는 1~3번이 모두 부수므로 2를 빼준다.

소스 코드

import sys
from collections import deque as Deque

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

def bfs(matrix, x, y):
    new_matrix = [[int(10e9)] * len(matrix[0]) for _ in range(len(matrix))]
    deque = Deque([[x, y]])
    dx, dy = [-1, 1, 0, 0], [0, 0, 1, -1]
    R, C = len(matrix), len(matrix[0])
    visited = [[False] * C for _ in range(R)]
    visited[x][y] = True
    new_matrix[x][y] = 0
    while deque:
        cx, cy = deque.popleft()
        for i in range(4):
            nx, ny = cx + dx[i], cy + dy[i]
            if 0 <= nx and nx < R and 0 <= ny and ny < C:
                if not visited[nx][ny] and matrix[nx][ny] == '.':
                    new_matrix[nx][ny] = new_matrix[cx][cy]
                    deque.appendleft([nx, ny])
                elif not visited[nx][ny] and matrix[nx][ny] == '#':
                    new_matrix[nx][ny] = new_matrix[cx][cy]+1
                    deque.append([nx, ny])
                visited[nx][ny] = True
    return new_matrix

for _ in range(T):
    h, w = map(int, input().split())
    matrix = [list('.'+input()+'.') for _ in range(h)]
    matrix = [['.'] * (w+2)] + matrix + [['.'] * (w+2)]
    player = []
    for i in range(len(matrix)):
        for j in range(len(matrix[0])):
            if matrix[i][j] == '$':
                player.append([i, j])
                matrix[i][j] = '.'
                
    playerA, playerB = player[0], player[1]
    matrix1 = bfs(matrix, 0, 0)
    matrix2 = bfs(matrix, playerA[0], playerA[1])
    matrix3 = bfs(matrix, playerB[0], playerB[1])

    answer = int(10e9)
    for i in range(len(matrix)):
        for j in range(len(matrix[0])):
            if matrix[i][j] == '*':
                continue
            sumation = matrix1[i][j] + matrix2[i][j] + matrix3[i][j]
            if matrix[i][j] == '#':
                answer = min(answer, sumation-2)
            else:
                answer = min(answer, sumation)

    print(answer)

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

풀이 과정

1. 2차원 DP 테이블을 구성한다.
   1. DP[i][0]: i번째 스티커를 붙이지 않았을 때 최대 점수
   2. DP[i][1]: i번째 스티커를 윗줄에 붙였을 때 최대 점수
   3. DP[i][2]: i번째 스티커를 아랫줄에 붙였을 때 최대 점수
2. 점화식을 구해준다.
   1. 예시로 DP[i][0]의 경우는 i번째 스티커를 붙이지 않을 때의 경우이므로 DP[i-1][0], DP[i-1][1], DP[i-1][2]중 최댓값과 같다.
   2. DP[i][1]이나 DP[i][2]를 구할 때는, 현재 스티커의 점수를 더해서 저장해주어야 한다.
3. 테이블을 모두 구성하면 DP 테이블의 맨 마지막 행의 최댓값을 구해서 출력시켜준다.

소스 코드 

import sys

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

for _ in range(T):
    N = int(input())
    scoreA = list(map(int, input().split()))
    scoreB = list(map(int, input().split()))
    DP = [[0] * 3 for _ in range(N)]
    DP[0][0], DP[0][1], DP[0][2] = 0, scoreA[0], scoreB[0]
    for i in range(1, N):
        DP[i][0] = max(DP[i-1][0], DP[i-1][1], DP[i-1][2])
        DP[i][1] = max(DP[i-1][0], DP[i-1][2]) + scoreA[i]
        DP[i][2] = max(DP[i-1][0], DP[i-1][1]) + scoreB[i]

    print(max(DP[N-1]))

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

풀이 과정

1. BFS 알고리즘을 사용하여 크기가 가장 큰 블록 그룹을 찾는다.
   1. 이 때, 크기가 같은 경우 무지개 블록의 수를 비교하여서 갱신시킨다.
   2. 기준 블록을 왼쪽 위에서 오른쪽 아래 순서로 골라서 블록 그룹을 찾으므로 현재 고른 블록이 기준 블록의 행이 가장 크고 열이 가장 큰 것이다. 따라서 크기가 같고 무지개 블록의 수도 같은 경우는 갱신시켜 주어야 한다.
2. (1)에서 구한 블록 그룹을 모두 제거한다. 이 때 점수도 같이 구해준다.
   • 제거 표시는 -2로 표시하고, 점수는 블록 그룹 내 블록의 수 제곱을 해준다.
3. 중력 기능을 구현한다.
   • 가장 아래 행에서부터 시작해서 하나하나의 요소들을 아래에 -2가 나타나지 않을때까지 당겨준다.
4. 회전 기능을 구현한다.
   • matrix[i][j] = matrix[j][len(matrix[0])-1-i]
5. 구현 순서에 맞추어서 전체 기능을 조합한다. 이 때, 최대 블록 그룹을 구했을 때, 그룹이 없거나 그룹 내 블록의 수가 1개인 경우에 게임을 종료시킨다.

소스 코드

import sys
from collections import deque
import copy


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

def bfs(matrix, startX, startY):
    dx = [-1, 1, 0, 0]
    dy = [0, 0, 1, -1]
    queue = deque([[startX, startY]])
    block_color = matrix[startX][startY]
    matrix[startX][startY] = -1
    block_count = 1
    rainbow = []
    block = [[startX, startY]]
    while queue:
        x, y = queue.popleft()
        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:
                if matrix[nx][ny] == block_color or matrix[nx][ny] == 0:
                    queue.append([nx, ny])
                    block.append([nx, ny])
                    block_count += 1
                    if matrix[nx][ny] == 0:
                        rainbow.append([nx, ny])
                    matrix[nx][ny] = -1

    for nx, ny in rainbow:
        matrix[nx][ny] = 0

    return block, block_count, len(rainbow)

def find_max_block(target):
    matrix = copy.deepcopy(target)
    max_block, max_block_count, max_rainbow = None, 0, 0
    for i in range(len(matrix)):
        for j in range(len(matrix[0])):
            if matrix[i][j] > 0:
                block, block_count, rb_len = bfs(matrix, i, j)
                if max_block_count < block_count:
                    max_block, max_block_count, max_rainbow = block, block_count, rb_len
                elif max_block_count == block_count:
                    if max_rainbow <= rb_len:
                        max_block, max_block_count, max_rainbow = block, block_count, rb_len

    return max_block

def destroy(matrix, block):
    for x, y in block:
        matrix[x][y] = -2

def gravity(matrix):
    for i in range(len(matrix)-2, -1, -1):
        for j in range(len(matrix[0])):
            index = i
            if matrix[i][j] == -1:
                continue
            while index+1 != N and matrix[index+1][j] == -2:
                matrix[index+1][j] = matrix[index][j]
                matrix[index][j] = -2
                index += 1

def rotate(matrix):
    new_matrix = copy.deepcopy(matrix)
    for i in range(len(matrix)):
        for j in range(len(matrix[0])):
            new_matrix[i][j] = matrix[j][len(matrix)-1-i]

    return new_matrix
            

score = 0

while True:
    block = find_max_block(matrix)
    if block == None:
        break
    if len(block) <= 1:
        break
    score += (len(block) ** 2)
    destroy(matrix, block)
    gravity(matrix)
    matrix = rotate(matrix)
    gravity(matrix)

print(score)

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

풀이 과정

1. 입력받은 순서대로 미네랄을 하나 없애준다. 이 때 왼쪽, 오른쪽 순으로 없애는 것에 유의
2. 각각의 미네랄을 기준으로 bfs를 진행해서 블록들을 구해준다.
   1. 이 때, 블록이 바닥에 닿지 않는다면, 해당 블록을 이동시켜주어야 하니 잠시 저장시켜 둔다.
3. 바닥에 닿지 않는 블록이 있는 경우, 바닥에 닿지 않는 블록들을 몇칸 내려야 다른 블록에 충돌하는지 벽에 닿는지 검사하고, 해당 칸수만큼 블록 내 모든 미네랄들을 내려준다.
4. 1-3번 과정을 반복한다.

소스 코드

import sys
from collections import deque
import copy

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

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

def bfs(matrix, sx, sy):
    dx = [-1, 1, 0, 0]
    dy = [0, 0, 1, -1]
    block = [[sx, sy]]
    queue = deque([[sx, sy]])
    matrix[sx][sy] = '.'
    down = False if sx == R-1 else True
    while queue:
        sx, sy = queue.popleft()
        for i in range(4):
            nx, ny = sx + dx[i], sy + dy[i]
            if nx >= 0 and nx < R and ny >= 0 and ny < C and \
               matrix[nx][ny] == 'x':
                down = False if nx == R-1 else down
                block.append([nx, ny])
                queue.append([nx, ny])
                matrix[nx][ny] = '.'

    return block, down
    

def movedown(matrix, block):
    for x, y in block:
        matrix[x][y] = '.'
    movement_count = 0
    # 몇칸 이동해야하는지 구함
    for i in range(1, R):
        for x, y in block:
            if x+i+1 == R or matrix[x+i+1][y] == 'x':
                movement_count = i
                break
        if movement_count != 0:
            break

    for x, y in block:
        matrix[x+movement_count][y] = 'x'
    

def check(matrix):
    target = None
    cp_matrix = copy.deepcopy(matrix)
    for i in range(len(cp_matrix)):
        for j in range(len(cp_matrix[0])):
            if cp_matrix[i][j] == 'x':
                block, down = bfs(cp_matrix, i, j)
                if down:
                    target = block
                    break
        if target:
            break

    if target:
        movedown(matrix, target)

left = True
for throw in throws:
    if left:
        for j in range(C):
            if matrix[R-throw][j] == 'x':
                matrix[R-throw][j] = '.'
                break
    else:
        for j in range(C-1, -1, -1):
            if matrix[R-throw][j] == 'x':
                matrix[R-throw][j] = '.'
                break
    check(matrix)
    left = not left

for m in matrix:
    print("".join(m))

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

풀이 과정

1. 임의의 수를 두개 고른 다음, 두 수의 합의 부호를 반전시켜 준다.
2. 반전시켜 준 값이 고른 두개의 수 위치 뒤에 있는지 확인한다.
   1. 있다면, 값이 여러개일 수 있으므로 이분 탐색을 두번 진행한다.
   2. bisect_left로 왼쪽 위치를 구해주고, bisect_right로 오른쪽 위치를 구해준 다음 두 값의 차이만큼 정답에 더해준다.
   3. bisect_left의 경우 값이 존재하는 맨 왼쪽 위치가 리턴되고, bisect_right의 경우 값이 존재하는 맨 오른쪽 위치 + 1이 존재하므로 bisect_right의 결과에서 bisect_left의 결과를 빼주면 동일한 값의 개수가 나온다.

소스 코드

import sys
from bisect import bisect_left, bisect_right

input = lambda: sys.stdin.readline().rstrip()
N = int(input())
numbers = list(map(int, input().split()))
numbers.sort()
cache = set(numbers)
answer = 0
for i in range(N):
    for j in range(i+1, N):
        target = -(numbers[i] + numbers[j])
        if target in cache:
            answer += bisect_right(numbers, target, j+1, N) - bisect_left(numbers, target, j+1, N)

print(answer)

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

풀이 과정

1. 사용 가능한 로마 숫자가 1, 5, 10, 50이며, N개의 숫자를 모두 사용했을 때 서로 다른 수의 개수를 출력
2. 따라서, 너비우선 탐색을 통해 만들 수 있는 서로 다른 수를 모두 구해준다.
   1. 중복이 있을 수 있으므로 SET 자료구조를 사용한다.
   2. 큐에 있는 각 숫자들을 하나씩 빼면서 1, 5, 10, 50을 더한 값을 중복 제거를 위해 임시로 set에 넣어준다.
   3. 큐가 비게 되면, set에 있는 값들을 큐에 넣어준다.
   4. 2-3 과정을 N번 반복해준 다음 최종적으로 set에 저장된 값의 개수를 출력시켜 준다.

소스 코드

import sys
from collections import deque

input = lambda: sys.stdin.readline().rstrip()
n = int(input())
numbers = [1, 5, 10, 50]

def solve():
    queue = deque([0])
    step = 0
    middle = set()
    answer = set()
    while True:
        x = queue.popleft()
        for num in numbers:
            middle.add(x+num)
        if not queue:
            step += 1
            if step == n:
                answer = middle
                break
            else:
                queue = deque(middle)
                middle = set()

    return len(answer)
    
print(solve())

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

풀이 과정

1. & 연산의 경우 두 비트가 모두 1일때만 1, 아닐때는 0으로 설정한다는 점을 이용
2. 따라서, 우선 비트의 개수를 저장해 둘 배열을 만들어 둔다.
   1. array[0] : 0번째 자리에서 비트 1의 개수, ..
3. 각각의 수를 모두 2진수로 바꾼 다음 각 자리를 검사하면서 비트가 1인 경우, 배열의 해당 자리 값을 1 증가시킨다.
4. &연산의 결과가 0이 되지 않으려면, 연산을 하는 값들의 비트중 하나라도 모두 1이 나와야 한다. 따라서 1이 가장 많이 나온 자리를 찾아주어야 하므로, 배열의 최댓값을 구한다.

소스 코드

import sys

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

n = int(input())
sequence = list(map(int, input().split()))
bit_count = [0] * 32

def calc_bit(a):
    temp = a
    n = 0
    while temp > 0:
        bit_count[n] += (temp % 2)
        temp = temp // 2
        n += 1

for item in sequence:
    calc_bit(item)

print(max(bit_count))

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

풀이 과정

1. 주어진 문제 (100+1+ | 01)+로 DFA를 구성한다.
   1. 100+1+에서 마지막에 0이 나온 경우, 100+1+로 이동할지 01로 이동할지 알수 없음.
   2. 따라서, 100+1+에서 1과 0을 추가로 만들어 주어서 1->0->0->1->1->0으로 구성
   3. 네번째 1에서 0이 나온 경우는 01로 이동, 여섯번째 0에서 0이 나온 경우는 세번째 0으로 이동하도록 DFA 구성
2. 각각의 테스트 케이스에 대하여 오토마타를 타고 넘어가본다. 이 때, 실패하는 케이스에 대해서는 바로 NO를 출력시켜 주고 다음 테스트 케이스를 진행한다.
3. 최종적으로 종료상태에 들어간 경우에만 YES를 출력해주고, 종료상태에 들어가지 않은 경우 NO를 출력시켜 준다.

소스 코드

import sys

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

n = int(input())
total_case = list()
for _ in range(n):
    s = input()
    automata = 'S'
    for ch in s:
        if automata == 'S':
            if ch == '1':
                automata = 1
            else:
                automata = 2
                
        elif automata == 1:
            if ch == '1':
                print('NO')
                break
            else:
                automata = 3
                
        elif automata == 2:
            if ch == '1':
                automata = 7
            else:
                print('NO')
                break
            
        elif automata == 3:
            if ch == '0':
                automata = 4
            else:
                print('NO')
                break
            
        elif automata == 4:
            if ch == '0':
                continue
            else:
                automata = 5
                
        elif automata == 5:
            if ch == '0':
                automata = 2
            else:
                automata = 6
                
        elif automata == 6:
            if ch == '0':
                automata = 8
            else:
                continue
            
        elif automata == 7:
            if ch == '0':
                automata = 2
            else:
                automata = 1
                
        elif automata == 8:
            if ch == '0':
                automata = 4
            else:
                automata = 7
    else:
        if automata == 7 or automata == 5 or automata == 6:
            print('YES')
        else:
            print('NO')

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

풀이 과정

1. 전체적인 과정은 Recursion으로 진행한다.
2. 현재 위치에 넴모를 넣을수 있으면 넣어보고, 넣을수 없으면 넣지 않고 다음 위치로 이동한다.
3. 이 때, 넴모를 넣었는지 넣지 않았는지 확인하기 위한 격자판을 미리 만들어두고 넴모를 넣었을때 1, 넣지 않았을때 0으로 설정한다.
4. 현재 위치 기준으로 왼쪽, 왼쪽위, 위에 넴모가 있는지 확인하고, 넴모가 모두 있으면 현재 위치엔 넣을수 없으므로 넣지 않고, 넴모가 한군데라도 없다면 현재 위치에 넣을 수 있으므로 넣는다.
5. 넴모를 넣을때마다 정답을 하나씩 증가시켜서 마지막에 전체 경우의 수를 출력시켜 준다.

쉬운 문제인거 같은데 뭔가 많이 헤맸던것 같다.. 넴모의 위치를 처음에는 Set으로 했었는데.. 계속해서 시간초과에 걸려서 행렬로 바꾸었음, 그래도 시간초과에 걸려서 원래 현재 위치 기준으로 삽입할 수 있는지 체크하는걸 함수로 구현하였었는데, 함수에서 일반 비교식으로 바꾸니 시간 초과가 걸리지 않음.

소스 코드

import sys

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

block_set = set()
matrix = [[0] * (M+1) for _ in range(N+1)]

def solve(i, j):
    answer = 0
    if j > M:
        i, j = i+1, 1
    if i > N:
        return 0
    
    if matrix[i-1][j] == 0 or matrix[i][j-1] == 0 or matrix[i-1][j-1] == 0:
        matrix[i][j] = 1
        answer += (1 + solve(i, j+1))
        matrix[i][j] = 0
    answer += solve(i, j+1)

    return answer

print(solve(1, 1) + 1)

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

풀이 과정

1. 전반적인 과정은 BFS로 진행
   1. 루트 노드(1)부터 시작한다.
   2. 현재 노드에서 연결된 자식 노드 수만큼 물을 나누어서 배분시켜 준다.
   3. 나누어준 자식 노드로 이동하여서 다음 자식노드에게 물을 나누어준다.
   4. 2-3 과정을 반복한다.
2. 이 때, 자식노드가 존재하여 자식노드에게 물을 나누어준 경우에는 비교를 위해 값을 0으로 설정한다. 소숫점 비교는 잘 되지 않음.
3. BFS가 종료되면, 물의 양의 합계 / 물의 양이 0이 아닌 노드의 갯수 를 출력시켜 준다.

소스 코드

import sys
from collections import deque

input = lambda: sys.stdin.readline().rstrip()
N, W = map(int, input().split())
t = [[] for _ in range(N+1)]
v = [0] * (N+1)
v[1] = W

for _ in range(N-1):
    a, b = map(int, input().split())
    t[a].append(b)
    t[b].append(a)

visited = set()
visited.add(1)
queue = deque([1])

while queue:
    node = queue.popleft()
    count = 0
    for nx in t[node]:
        if nx not in visited:
            count += 1

    if count == 0:
        continue

    each_value = v[node] / count
    for nx in t[node]:
        if nx not in visited:
            v[nx] = each_value
            visited.add(nx)
            queue.append(nx)
    v[node] = 0

count = 0
for i in range(1, N+1):
    if v[i] != 0:
        count += 1

print(sum(v) / count)