Jinho Tech

기본적인 BFS 문제이다. 

from collections import deque

def bfs(y, x):
    q = deque()
    q.append((y, x))
    graph[y][x] = '.'
    while q:
        y, x = q.popleft()
        for dy, dx in d:
            Y, X = y+dy, x+dx
            if (0 <= Y < r) and (0 <= X < c) and graph[Y][X] == '*':
                q.append((Y, X))
                graph[Y][X] = '.'

r, c = map(int, input().split())
graph = [list(input()) for _ in range(r)]
d = [(-1, 0), (1, 0), (0, -1), (0, 1)]
cnt = 0
for i in range(r):
    for j in range(c):
        if graph[i][j] == '*':
            bfs(i, j)
            cnt += 1
print(cnt)

정렬 & DFS 문제이다. 현재 회의가 끝나는 시간이 제일 늦은 회의 시작 시간보다 크면 더 이상 회의를 할 수 없는 상황이므로 여태까지 회의에 참여한 인원수를 리스트에 추가해준다. 마지막에 리스트의 최댓값을 출력해주면 끝이다.

import sys
sys.setrecursionlimit(3000000)

def dfs(node, t):
    t += li[node][2]
    if li[node][1] > max_s:
        res.append(t)        
    for n in range(node+1, N):
        if li[node][1] > li[n][0]:
            continue
        dfs(n, t)

N = int(input())
li = [list(map(int, input().split())) for _ in range(N)]
li.sort(key=lambda x:(x[0], x[1]))
res = []
max_s = max([s for s, e, n in li])
for i in range(N):
    dfs(i, 0)
print(max(res))

기본적인 BFS 문제이다.

from collections import deque

def bfs(y, x):
    q = deque()
    q.append((y, x))
    graph[y][x] = '1'
    while q:
        y, x = q.popleft()
        for dy, dx in d:
            Y, X = y+dy, x+dx
            if (0 <= Y < R) and (0 <= X < C) and graph[Y][X] == '#':
                q.append((Y, X))
                graph[Y][X] = '1'

R, C = map(int, input().split())
graph = [list(input()) for _ in range(R)]
d = [(-1, 0), (1, 0), (0, -1), (0, 1)]
cnt = 0
for i in range(R):
    for j in range(C):
        if graph[i][j] == '#':
            bfs(i, j)
            cnt += 1
print(cnt)

생각보다 어려운 BFS 문제이다. 바이러스가 퍼지는 순서(작은 숫자부터)에 맞게

def bfs(x, y):
    check[x][y] = 1
    for dx, dy in d:
        X, Y = x+dx, y+dy
        if (0 <= X < N) and (0 <= Y < N) and graph[X][Y] == 0:
            check[X][Y] = 1
            graph[X][Y] = graph[x][y]

N, K = map(int, input().split())
graph = [list(map(int, input().split())) for _ in range(N)]
S, X, Y = map(int, input().split())
d = [(-1, 0), (1, 0), (0, -1), (0, 1)]
check = [[0]*N for _ in range(N)]
while S:
    li = []
    for i in range(N):
        for j in range(N):
            if graph[i][j] > 0:
                li.append([i, j])
    li.sort(key=lambda x:graph[x[0]][x[1]])
    for i, j in li:
        bfs(i, j)
    if graph[X-1][Y-1]:
        break
    S -= 1
print(graph[X-1][Y-1])

구현 & BFS 문제이다. 거리가 2 이상 3 이하인 노드의 개수를 출력해주면 된다.

from collections import deque

def bfs(node):
    queue = deque()
    queue.append(node)
    while queue:
        node = queue.popleft()
        for n in graph[node]:
            if check[n] == 0:
                check[n] = check[node]+1
                queue.append(n)
    
n = int(input())
m = int(input())
graph = [[] for _ in range(n+1)]
for _ in range(m):
    u, v = map(int, input().split())
    graph[u].append(v)
    graph[v].append(u)
check = [0]*(n+1)
check[1] = 1
bfs(1)
res = sum([1 for t in check if 2 <= t <= 3])
print(res)

구현 & DFS & BFS 문제이다. 기업 코딩 테스트에서 나올 것 같은 문제인데 참 재밌게 푼 것 같다.

1. 터트릴 뿌요가 있는지 확인하는 함수(같은 색깔의 뿌요가 4개 이상 뭉쳐 있는지 확인)

2. 뿌요를 터트려주는 함수('RGBPY' -> '0')

3. 상태를 업데이트해주는 함수(터진 뿌요가 있을 시 그 위치보다 위에 있는 뿌요들을 밑으로 내림)

위 3개의 함수를 구현해서 해결했다.

DFS 풀이

import sys
from copy import deepcopy
sys.setrecursionlimit(300000)

def dfs_check(y, x, color, cnt):
    b[y][x] = '0'
    for dy, dx in d:
        Y, X = y+dy, x+dx
        if (0 <= Y < 12) and (0 <= X < 6) and b[Y][X] == color:
            cnt = dfs_check(Y, X, color, cnt+1)
    return cnt


def dfs(y, x, color):
    a[y][x] = '0'
    for dy, dx in d:
        Y, X = y+dy, x+dx
        if (0 <= Y < 12) and (0 <= X < 6) and a[Y][X] == color:
            dfs(Y, X, color)
            
def update():
    for j in range(6):
        for i in range(12):
            if a[i][j] == '0':
                up = a[0][j]
                for k in range(i):
                    down = a[k+1][j]
                    a[k+1][j] = up
                    up = down
                a[0][j] = '.'
            
graph = [list(input()) for _ in range(12)]
a = deepcopy(graph) 
d = [(-1, 0), (1, 0), (0, -1), (0, 1)]
combo = 0
while 1:    
    b, ok = deepcopy(a), 0
    for i in range(12):
        for j in range(6):
            if a[i][j] in 'RGBPY':
                if dfs_check(i, j, a[i][j], 1) >= 4:
                    dfs(i, j, a[i][j])
                    ok = 1
    update()
    if ok == 0:
        break
    combo += 1
print(combo)

BFS 풀이

from collections import deque
from copy import deepcopy

def bfs_check(y, x, color):
    queue = deque()
    queue.append((y, x))
    b[y][x] = '0'
    cnt = 1
    while queue:
        y, x = queue.popleft()
        for dy, dx in d:
            Y, X = y+dy, x+dx
            if (0 <= Y < 12) and (0 <= X < 6) and b[Y][X] == color:
                b[Y][X] = '0'
                queue.append((Y, X))                
                cnt += 1
    return cnt

def bfs(y, x, color):
    queue = deque()
    queue.append((y, x))
    a[y][x] = '0'
    while queue:
        y, x = queue.popleft()
        for dy, dx in d:
            Y, X = y+dy, x+dx
            if (0 <= Y < 12) and (0 <= X < 6) and a[Y][X] == color:
                queue.append((Y, X))                
                a[Y][X] = '0'
            
def update():
    for j in range(6):
        for i in range(12):
            if a[i][j] == '0':
                up = a[0][j]
                for k in range(i):
                    down = a[k+1][j]
                    a[k+1][j] = up
                    up = down
                a[0][j] = '.'
            
graph = [list(input()) for _ in range(12)]
a = deepcopy(graph) 
d = [(-1, 0), (1, 0), (0, -1), (0, 1)]
combo = 0
while 1:    
    b, ok = deepcopy(a), 0
    for i in range(12):
        for j in range(6):
            if a[i][j] in 'RGBPY':
                if bfs_check(i, j, a[i][j]) >= 4:
                    bfs(i, j, a[i][j])
                    ok = 1                
    update()
    if ok == 0:
        break
    combo += 1
print(combo)

문제의 제목이 사칙연산인 단순 사칙연산 문제이다.

for _ in range(int(input())):
    li = input().split()
    a, b, c = int(li[0]), int(li[2]), int(li[4])
    op = li[1]
    if op == '+':
        t = a+b
    elif op == '-':
        t = a-b
    elif op == '*':
        t = a*b
    elif op == '/':
        t = a//b
    print("correct" if t == c else "wrong answer")

단순 사칙연산 문제이다. EOF까지 입력이 들어와서 try, except를 사용해줘야 한다.

s = ''
while 1:
    try:
        s += input()
    except:
        break
print(sum(map(int, s.split(','))))

단순 사칙연산 문제이다. bin(min(a, b))[::-1].index('1') 이 핵심이다. 파이썬이라서 가능한 풀이인 것 같다.

다른 언어면 절대 이렇게 쉽게 못 구현한다.

for _ in range(int(input())):
    n, a, b = map(int, input().split())
    t = bin(min(a, b))[::-1].index('1')
    print(n-t)

단순 사칙연산 문제이다.

k = int(input())
t = 2**k - 1
res = t*(t+1)//2
print(bin(res)[2:])

단순 사칙연산 문제이다.

2013년이 계사년 즉 1984년이 주기의 시작인 갑자년이므로 1984를 사용하면 쉽게 풀 수 있다. 

N = int(input())
t = (N-1984)%60
res = "ABCDEFGHIJKL"[t%12] + str(t%10)
print(res)

단순 사칙연산 & 구현 문제이다.

i = 1
while 1:
    n = int(input())
    if n == 0:
        break
    li = list(map(int, input().split()))
    cnt = 0
    while li != [li[0]]*n:
        max_i = li.index(max(li))
        li[max_i] -= 1
        min_i = li.index(min(li))
        li[min_i] += 1
        cnt += 1
    print(f"Set #{i}")
    print(f"The minimum number of moves is {cnt}.")
    print()
    i += 1

단순 사칙연산 문제이다.

i = 1
while 1:
    li = list(map(int, input().split()))
    if li[0] == 0:
        break
    r, w, l = li
    d = (w/2)**2 + (l/2)**2
    if r**2 >= d:
        print(f"Pizza {i} fits on the table.")
    else: 
        print(f"Pizza {i} does not fit on the table.")
    i += 1

단순 구현 문제이다.

while 1:
    n = input()
    if n == '0':
        break
    while len(n) > 1:
        res = 1
        print(n, end=' ')
        for c in n:
            res *= int(c)
        n = str(res)
    print(n)

단순 문자열 문제이다.

for _ in range(int(input())):
    s = list(input())
    s[0] = s[0].upper()
    print(''.join(s))