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

문제 설명

문제

N(2 ≤ N ≤ 10,000)개의 섬으로 이루어진 나라가 있다. 이들 중 몇 개의 섬 사이에는 다리가 설치되어 있어서 차들이 다닐 수 있다.

영식 중공업에서는 두 개의 섬에 공장을 세워 두고 물품을 생산하는 일을 하고 있다. 물품을 생산하다 보면 공장에서 다른 공장으로 생산 중이던 물품을 수송해야 할 일이 생기곤 한다. 그런데 각각의 다리마다 중량제한이 있기 때문에 무턱대고 물품을 옮길 순 없다. 만약 중량제한을 초과하는 양의 물품이 다리를 지나게 되면 다리가 무너지게 된다.

한 번의 이동에서 옮길 수 있는 물품들의 중량의 최댓값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N, M(1 ≤ M ≤ 100,000)이 주어진다. 다음 M개의 줄에는 다리에 대한 정보를 나타내는 세 정수 A, B(1 ≤ A, B ≤ N), C(1 ≤ C ≤ 1,000,000,000)가 주어진다. 이는 A번 섬과 B번 섬 사이에 중량제한이 C인 다리가 존재한다는 의미이다. 서로 같은 두 섬 사이에 여러 개의 다리가 있을 수도 있으며, 모든 다리는 양방향이다. 마지막 줄에는 공장이 위치해 있는 섬의 번호를 나타내는 서로 다른 두 정수가 주어진다. 공장이 있는 두 섬을 연결하는 경로는 항상 존재하는 데이터만 입력으로 주어진다.

출력

첫째 줄에 답을 출력한다.

풀이 과정

• 다익스트라 알고리즘을 다르게 적용하여서 풀이함.
  • 최소 비용 -> 최대 비용

1. 기본적으로 다익스트라 알고리즘 사용

   • 연결된 노드들 중에서 중량이 최댓값인 노드 선택
   • 해당 노드에 연결된 인접 노드들의 중량 갱신 / 히프에 추가

2. 기존에는 그냥 deque를 사용하였으나.. 시간 초과 문제가 생김.

   • 최대 히프 사용하여 중량이 가장 큰 노드부터 방문
   • 이미 갱신된 경우, 생략하는 과정 추가

3. 목표 지점의 중량 출력

소스 코드

import sys
from collections import deque
import heapq

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

graph = [[] for _ in range(N+1)]

for _ in range(M):
    a, b, weight = map(int, input().rstrip().split())
    graph[a].append([b, weight])
    graph[b].append([a, weight])

start, end = map(int, input().rstrip().split())

INT_MAX = int(10e9)
distance = [0] * (N+1)
heap = [[-INT_MAX, start]]
distance[start] = INT_MAX

while heap:
    cost, node = heapq.heappop(heap)
    cost = -cost

    # 이미 갱신된 경우라면 생략
    if distance[node] > cost:
        continue

    for next_node, next_cost in graph[node]:
        new_cost = min(cost, next_cost)
        # 기존 무게보다 현재 거쳤을때의 무게가 더 크다면 갱신
        if distance[next_node] < new_cost:
            distance[next_node] = new_cost
            heapq.heappush(heap, [-new_cost, next_node])

print(distance[end])

문제

민혁이는 소셜 네트워크 사이트에서 친구를 만드는 것을 좋아하는 친구이다. 우표를 모으는 취미가 있듯이, 민혁이는 소셜 네트워크 사이트에서 친구를 모으는 것이 취미이다.

어떤 사이트의 친구 관계가 생긴 순서대로 주어졌을 때, 두 사람의 친구 네트워크에 몇 명이 있는지 구하는 프로그램을 작성하시오.

친구 네트워크란 친구 관계만으로 이동할 수 있는 사이를 말한다.

입력

첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스의 첫째 줄에는 친구 관계의 수 F가 주어지며, 이 값은 100,000을 넘지 않는다. 다음 F개의 줄에는 친구 관계가 생긴 순서대로 주어진다. 친구 관계는 두 사용자의 아이디로 이루어져 있으며, 알파벳 대문자 또는 소문자로만 이루어진 길이 20 이하의 문자열이다.

출력

친구 관계가 생길 때마다, 두 사람의 친구 네트워크에 몇 명이 있는지 구하는 프로그램을 작성하시오.

풀이 과정

1. 이전에 나타나지 않은 인원의 경우 딕셔너리에 넣어준다.
   • 딕셔너리에 넣어주면서 parent 설정, 인원수 1명(자기 자신) 설정
2. 입력받은 두명의 그룹을 합친다.
   • 이 때, 두명이 속한 그룹의 인원수도 같이 합쳐주어야 함.
   • 인원수를 따로 구하려고 하면 시간 초과가 나온다.
3. 매 과정마다 그룹 내의 인원수를 출력해준다.

• 처음에는 인원수를 따로 for문으로 구하려고 했는데 시간초과가 나옴..
• 처음 시간초과가 났을 때는 차라리 set을 사용해서 구현하는 것이 더 편할거 같았으나..
  Union-Find로 통과받아보고 싶어서 매달림,,

소스 코드

import sys
input = sys.stdin.readline

total_case = int(input().rstrip())

def find(parent, group, a):
    if parent[a] != a:
        parent[a] = find(parent, group, parent[a])
        group[a] = group[parent[a]]
    return parent[a]

def union(parent, group, a, b):
    p1 = find(parent, group, a)
    p2 = find(parent, group, b)
    if p1 < p2:
        parent[p2] = p1
    else:
        parent[p1] = p2

for i in range(total_case):
    F = int(input().rstrip())
    member = dict()
    count = 0
    parent = [-1] * 200001
    group = [0] * 200001
    for _ in range(F):
        person1, person2 = input().rstrip().split()

        # 새로운 멤버 추가
        if member.get(person1) == None:
            parent[count] = count
            member[person1] = count
            group[count] = 1
            count += 1
        if member.get(person2) == None:
            parent[count] = count
            member[person2] = count
            group[count] = 1
            count += 1

        # 두 그룹 합침
        par1 = find(parent, group, member[person1])
        par2 = find(parent, group, member[person2])
        if par1 != par2:
            union(parent, group, par1, par2)
            # 그룹 인원수 합침
            temp = group[par1] + group[par2]
            group[par1] = temp
            group[par2] = temp

        # 위 과정에서는 부모의 그룹 인원수만 바뀌므로   
        # find 한번 더 호출해서 자식들의 그룹 멤버 수가 부모의 그룹 인원수가 되도록 조정
        find(parent, group, member[person1])
        find(parent, group, member[person2])

        group_count = group[member[person1]]
        print(group_count)

문제

국가의 역할 중 하나는 여러 지방의 예산요청을 심사하여 국가의 예산을 분배하는 것이다. 국가예산의 총액은 미리 정해져 있어서 모든 예산요청을 배정해 주기는 어려울 수도 있다. 그래서 정해진 총액 이하에서가능한 한 최대의총 예산을 다음과 같은 방법으로 배정한다.

1. 모든 요청이 배정될 수 있는 경우에는 요청한 금액을 그대로 배정한다.
2. 모든 요청이 배정될 수 없는 경우에는 특정한정수상한액을 계산하여 그 이상인 예산요청에는 모두 상한액을 배정한다. 상한액 이하의 예산요청에 대해서는 요청한 금액을 그대로 배정한다.

예를 들어, 전체 국가예산이 485이고 4개 지방의 예산요청이 각각 120, 110, 140, 150이라고 하자. 이 경우, 상한액을 127로 잡으면, 위의 요청들에 대해서 각각 120, 110, 127, 127을 배정하고 그 합이 484로 가능한 최대가 된다.

여러 지방의 예산요청과 국가예산의 총액이 주어졌을 때, 위의 조건을 모두 만족하도록 예산을 배정하는 프로그램을 작성하시오.

입력

첫째 줄에는 지방의 수를 의미하는 정수 N이 주어진다. N은 3 이상 10,000 이하이다. 다음 줄에는 각 지방의 예산요청을 표현하는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 값들은 모두 1 이상 100,000 이하이다. 그 다음 줄에는 총 예산을 나타내는 정수 M이 주어진다. M은 N 이상 1,000,000,000 이하이다.

출력

첫째 줄에는 배정된 예산들 중 최댓값인 정수를 출력한다.

풀이 과정

1. 범위를 0 ~ 예산요청의 최댓값으로 잡고 이분 탐색 진행
   • 중간값을 기준으로 예산 배정이 성공적으로 이루어지면 최댓값을 구해야 하므로 예산을 더 늘려보아야 한다. 따라서 저장 후 오른쪽 구간 (중간값+1 ~ )
   • 중간값을 기준으로 예산 배정이 성공적으로 이루어지지 않았다면 예산을 줄여야 하므로 왼쪽 구간 ( ~ 중간값-1)
2. 예산 배정 과정
   • 배정된 예산 > 예산요청 => 예산 요청
   • 배정된 예산 < 예산요청 => 배정된 예산
   • if문 작성에 유의

소스 코드

import sys

input = sys.stdin.readline

N = int(input().rstrip())
lists = list(map(int, input().rstrip().split()))
M = int(input().rstrip())

left = 0
right = max(lists)
answer = 0
while left <= right:
    mid = (left + right) // 2
    total = M
    succeed = True
    for k in lists:
        if (total < mid and k >= mid) or (
            total < k and k < mid ):
            succeed = False
        if succeed:
            if k < mid: # 현재 값보다 리스트 요소가 작으면 k만큼 빼줌
                total -= k
            else: # 현재 값보다 리스트 요소가 크면 현재 값만큼 빼줌
                total -= mid
        else:
            break

    if succeed:
        answer = mid
        left = mid+1
    else:
        right = mid-1

print(answer)    

문제 설명

문제

19학번 이준석은 학생이 N명인 학교에 입학을 했다. 준석이는 입학을 맞아 모든 학생과 친구가 되고 싶어한다. 하지만 준석이는 평생 컴퓨터랑만 대화를 하며 살아왔기 때문에 사람과 말을 하는 법을 모른다. 그런 준석이에게도 희망이 있다. 바로 친구비다!

학생 i에게Ai만큼의 돈을 주면 그 학생은 1달간 친구가 되어준다! 준석이에게는 총 k원의 돈이 있고 그 돈을 이용해서 친구를 사귀기로 했다. 막상 친구를 사귀다 보면 돈이 부족해질 것 같다는 생각을 하게 되었다. 그래서 준석이는 “친구의 친구는 친구다”를 이용하기로 했다.

준석이는 이제 모든 친구에게 돈을 주지 않아도 된다!

위와 같은 논리를 사용했을 때, 가장 적은 비용으로 모든 사람과 친구가 되는 방법을 구하라.

입력

첫 줄에 학생 수 N (1 ≤ N ≤ 10,000)과 친구관계 수 M (0 ≤ M ≤ 10,000), 가지고 있는 돈 k (1 ≤ k ≤ 10,000,000)가 주어진다.

두번째 줄에 N개의 각각의 학생이 원하는 친구비 Ai가 주어진다. (1 ≤ Ai ≤ 10,000, 1 ≤ i ≤ N)

다음 M개의 줄에는 숫자 v, w가 주어진다. 이것은 학생 v와 학생 w가 서로 친구라는 뜻이다.

출력

준석이가 모든 학생을 친구로 만들 수 있다면, 친구로 만드는데 드는 최소비용을 출력한다. 만약 친구를 다 사귈 수 없다면, “Oh no”(따옴표 제거)를 출력한다.

풀이 과정

• 문제지 분류에는 Union-Find로 나와 있는데, BFS로 푸는게 더 쉬울거 같아서 BFS로 풀이함.

1. 현재 기준 방문하지 않았으면서 비용이 가장 짧은 학생을 선택한 후, 연결된 모든 학생들을 BFS로 탐색
   • BFS로 탐색하면서 방문 처리 모두 해두어야 함.
2. 진행하다가 비용의 합계가 k보다 크다면 "Oh no" 출력
3. 모든 학생들이 방문 처리 되었다면 비용의 합계 출력

소스 코드

import sys
from collections import deque

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

costs = [0] + list(map(int, input().rstrip().split()))
visited = [False] * len(costs)

graph = [[] for _ in range(N+1)]

for i in range(M):
    a, b = map(int, input().rstrip().split())
    graph[a].append(b)
    graph[b].append(a)

def get_min_cost(costs, visited):
    cost = int(10e9)
    idx = -1
    for i in range(1, len(costs)):
        if not visited[i] and cost > costs[i]:
            cost = costs[i]
            idx = i

    return (cost, idx)
total = 0
while True:
    cost, idx = get_min_cost(costs, visited)
    if idx == -1:
        print(total)
        sys.exit(0)

    total += cost

    if total > k:
        print("Oh no")
        sys.exit(0)

    queue = deque([idx])
    visited[idx] = True
    while queue:
        node = queue.popleft()
        for g in graph[node]:
            if not visited[g]:
                queue.append(g)
                visited[g] = True

문제 설명

문제

삼각수 Tn(n ≥ 1)는 [그림]에서와 같이 기하학적으로 일정한 모양의 규칙을 갖는 점들의 모음으로 표현될 수 있다.

[그림]

자연수 n에 대해 n ≥ 1의 삼각수Tn는 명백한 공식이 있다.

Tn= 1 + 2 + 3 + ... + n = n(n+1)/2

1796년, 가우스는 모든 자연수가 최대 3개의 삼각수의 합으로 표현될 수 있다고 증명하였다. 예를 들어,

• 4 = T1+ T2
• 5 = T1+ T1+ T2
• 6 = T2+ T2or 6 = T3
• 10 = T1+ T2+ T3or 10 = T4

이 결과는 증명을 기념하기 위해 그의 다이어리에 “Eureka! num = Δ + Δ + Δ” 라고 적은것에서 유레카 이론으로 알려졌다. 꿍은 몇몇 자연수가 정확히 3개의 삼각수의 합으로 표현될 수 있는지 궁금해졌다. 위의 예시에서, 5와 10은 정확히 3개의 삼각수의 합으로 표현될 수 있지만 4와 6은 그렇지 않다.

자연수가 주어졌을 때, 그 정수가 정확히 3개의 삼각수의 합으로 표현될 수 있는지 없는지를 판단해주는 프로그램을 만들어라. 단, 3개의 삼각수가 모두 달라야 할 필요는 없다.

입력

프로그램은 표준입력을 사용한다. 테스트케이스의 개수는 입력의 첫 번째 줄에 주어진다. 각 테스트케이스는 한 줄에 자연수 K (3 ≤ K ≤ 1,000)가 하나씩 포함되어있는 T개의 라인으로 구성되어있다.

출력

프로그램은 표준출력을 사용한다. 각 테스트케이스에대해 정확히 한 라인을 출력한다. 만약 K가 정확히 3개의 삼각수의 합으로 표현될수 있다면 1을, 그렇지 않다면 0을 출력한다.

풀이 과정

1. 미리 삼각수를 1000까지 구해둔다. (입력 범위가 3~1000)이므로
2. 삼각수의 개수가 많지 않으므로 3중 반복문으로 모든 경우의 수를 구해준다.
   • i + j + k가 입력받은 값인지 검사
   • 그나마 조금이라도 효율성 높이기 위해 i, j, k 각각이 입력받은 값보다 크면 continue
3. i + j + k가 입력받은 값이 된다면 1, 되지 않는다면 0 출력

소스 코드

import sys

start = 1
add = 2
Triangle = []
while True:
    Triangle.append(start)
    start += add
    add += 1
    if start >= 1000:
        break

def check(a, Triangle):
    for i in Triangle:
        if i >= a: continue
        for j in Triangle:
            if j >= a: continue
            for k in Triangle:
                if k >= a: continue
                if i + j + k == a:
                    return True

    return False


count = int(sys.stdin.readline().rstrip())
for i in range(count):
    n = int(sys.stdin.readline().rstrip())
    if check(n, Triangle):
        print(1)
    else:
        print(0)

문제 설명

문제

올해 Z대학 컴퓨터공학부에 새로 입학한 민욱이는 학부에 개설된 모든 전공과목을 듣고 졸업하려는 원대한 목표를 세웠다. 어떤 과목들은 선수과목이 있어 해당되는 모든 과목을 먼저 이수해야만 해당 과목을 이수할 수 있게 되어 있다. 공학인증을 포기할 수 없는 불쌍한 민욱이는 선수과목 조건을 반드시 지켜야만 한다. 민욱이는 선수과목 조건을 지킬 경우 각각의 전공과목을 언제 이수할 수 있는지 궁금해졌다. 계산을 편리하게 하기 위해 아래와 같이 조건을 간소화하여 계산하기로 하였다.

한 학기에 들을 수 있는 과목 수에는 제한이 없다.
모든 과목은 매 학기 항상 개설된다.
모든 과목에 대해 각 과목을 이수하려면 최소 몇 학기가 걸리는지 계산하는 프로그램을 작성하여라.

입력

첫 번째 줄에 과목의 수 N(1≤N≤1000)과 선수 조건의 수 M(0≤M≤500000)이 주어진다. 선수과목 조건은 M개의 줄에 걸쳐 한 줄에 정수 A B 형태로 주어진다. A번 과목이 B번 과목의 선수과목이다. A<B인 입력만 주어진다. (1≤A<B≤N)

출력

1번 과목부터 N번 과목까지 차례대로 최소 몇 학기에 이수할 수 있는지를 한 줄에 공백으로 구분하여 출력한다.

풀이 과정

1. 위상 정렬 알고리즘 사용
   • 진입 차수가 0인 노드들을 방문한다.
   • 진입 차수가 0인 노드에 연결된 간선을 제거해준다.
   • 간선 제거로 인해 진입차수가 0이 되는 노드들을 다음에 방문한다.
2. 위 알고리즘 과정이 선수과목과 같음.
   • 자바1 -> 자바2를 들어야 한다고 가정
   • 자바1의 진입 차수는 0이고, 자바2의 진입 차수는 1이므로 자바1 먼저 방문하고, 자바2를 방문하여야 함.
3. 큐에 노드 뿐만 아니라 학기도 같이 저장하여 준 다음, 방문 시 각 과목의 학기를 따로 저장

풀이 과정

import sys
from collections import deque

input = sys.stdin.readline

N, M = map(int, input().rstrip().split())

graph = [[] for _ in range(N+1)]
indegree = [0] * (N+1)
semester = [0] * (N+1)
queue = deque()


for _ in range(M):
    src, dest = map(int, input().rstrip().split())
    graph[src].append(dest)
    indegree[dest] += 1

# 초기 진입차수가 0인 노드 등록 
for i in range(1, N+1):
    if indegree[i] == 0:
        queue.append([i, 1])

while queue:
    cur, sem = queue.popleft()
    semester[cur] = sem
    for n in graph[cur]:
        indegree[n] -= 1
        # 진입차수가 0이 되면 들을수 있는 과목이므로 넣어준다.
        if indegree[n] == 0:
            queue.append([n, sem+1])

print(*semester[1:])

문제 설명

문제

이진 검색 트리는 다음과 같은 세 가지 조건을 만족하는 이진 트리이다.

• 노드의 왼쪽 서브트리에 있는 모든 노드의 키는 노드의 키보다 작다.
• 노드의 오른쪽 서브트리에 있는 모든 노드의 키는 노드의 키보다 크다.
• 왼쪽, 오른쪽 서브트리도 이진 검색 트리이다.

전위 순회 (루트-왼쪽-오른쪽)은 루트를 방문하고, 왼쪽 서브트리, 오른쪽 서브 트리를 순서대로 방문하면서 노드의 키를 출력한다. 후위 순회 (왼쪽-오른쪽-루트)는 왼쪽 서브트리, 오른쪽 서브트리, 루트 노드 순서대로 키를 출력한다. 예를 들어, 위의 이진 검색 트리의 전위 순회 결과는 50 30 24 5 28 45 98 52 60 이고, 후위 순회 결과는 5 28 24 45 30 60 52 98 50 이다.

이진 검색 트리를 전위 순회한 결과가 주어졌을 때, 이 트리를 후위 순회한 결과를 구하는 프로그램을 작성하시오.

입력

트리를 전위 순회한 결과가 주어진다. 노드에 들어있는 키의 값은 106보다 작은 양의 정수이다. 모든 값은 한 줄에 하나씩 주어지며, 노드의 수는 10,000개 이하이다. 같은 키를 가지는 노드는 없다.

출력

입력으로 주어진 이진 검색 트리를 후위 순회한 결과를 한 줄에 하나씩 출력한다.

풀이 과정

1. 전위 순회는 루트를 먼저 순회하므로, 전위 순회한 순서대로 노드를 넣어서 이진 검색 트리를 만들면 문제와 똑같은 트리가 만들어 진다.
   • 현재 노드보다 작으면 왼쪽 자식 노드
   • 현재 노드보다 크면 오른쪽 자식 노드
   • 자식 노드가 None인 경우 거기다가 넣어준다.
2. 후위 순회의 경우 recursion으로 구현한다. (left -> right -> 루트)
3. 입력 종료 글자가 없으므로 try..except로 입력 종료

소스 코드

import sys

sys.setrecursionlimit(10**5)

class tree_node():
    def __init__(self, element):
        self.left = None
        self.right = None
        self.element = element


def push_tree(tree, element):
    if tree.element == None: # 맨 위 루트노드는 초깃값 None
        tree.element = element
    else:
        temp = tree_node(element)
        while True:
            # 현재 트리의 요소보다 입력값이 크면 오른쪽
            if tree.element < element:
                if tree.right == None:
                    tree.right = temp
                    break
                else:
                    tree = tree.right
            # 작으면 왼쪽
            else:
                if tree.left == None:
                    tree.left = temp
                    break
                else:
                    tree = tree.left

def post_order(tree):
    if tree == None:
        return
    post_order(tree.left)
    post_order(tree.right)
    print(tree.element)

Tree = tree_node(None)
while True:
    try:
        p = int(input())
        push_tree(Tree, p)
    except:
        break

post_order(Tree)

문제 설명

문제

정사각형으로 이루어져 있는 섬과 바다 지도가 주어진다. 섬의 개수를 세는 프로그램을 작성하시오.

한 정사각형과 가로, 세로 또는 대각선으로 연결되어 있는 사각형은 걸어갈 수 있는 사각형이다.

두 정사각형이 같은 섬에 있으려면, 한 정사각형에서 다른 정사각형으로 걸어서 갈 수 있는 경로가 있어야 한다. 지도는 바다로 둘러싸여 있으며, 지도 밖으로 나갈 수 없다.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다.

둘째 줄부터 h개 줄에는 지도가 주어진다. 1은 땅, 0은 바다이다.

입력의 마지막 줄에는 0이 두 개 주어진다.

풀이 과정

1. 일반적인 BFS는 상하좌우인데 이번 케이스는 대각선까지 고려해야 하는 경우
   • 전체 2차원배열 루프를 돌면서 [i][j] = 1이 될 때를 찾는다.
   • [i][j]부터 시작하여 연결된 모든 섬들의 값을 0으로 조정해준 다음, 섬의 개수를 1개 늘려준다.
   • 전체 배열을 돌때까지 반복
2. 섬의 개수를 출력해주면 된다.

소스 코드

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

def bfs(graph, x, y):
    queue = deque([[x, y]])
    graph[x][y] = 0
    # 상하좌우
    dx = [-1, 1, 0, 0] 
    dy = [0, 0, 1, -1]

    # 대각선
    dx2 = [1, 1, -1, -1]
    dy2 = [-1, 1, -1, 1]
    while queue:
        x, y = queue.popleft()
        for i in range(4):
            # 상하좌우
            nx, ny = x+dx[i], y+dy[i]
            if 0 <= nx and nx < len(graph) and (
                0 <= ny and ny < len(graph[0])
            ):
               if graph[nx][ny] != 0:
                   graph[nx][ny] = 0
                   queue.append([nx, ny])
            # 대각선
            nx, ny = x+dx2[i], y+dy2[i]
            if 0 <= nx and nx < len(graph) and (
                0 <= ny and ny < len(graph[0])
            ):
                if graph[nx][ny] != 0:
                    graph[nx][ny] = 0
                    queue.append([nx,ny])


while True:
    w, h = map(int, input().rstrip().split())
    if w == 0 and h == 0:
        break

    graph = [list(map(int, input().rstrip().split())) for _ in range(h)]
    answer = 0
    for i in range(h):
        for j in range(w):
            if graph[i][j] == 1:
                answer += 1
                bfs(graph, i, j)
    print(answer)

문제 설명

문제

상근이는 문자열에 폭발 문자열을 심어 놓았다. 폭발 문자열이 폭발하면 그 문자는 문자열에서 사라지며, 남은 문자열은 합쳐지게 된다.

폭발은 다음과 같은 과정으로 진행된다.

• 문자열이 폭발 문자열을 포함하고 있는 경우에, 모든 폭발 문자열이 폭발하게 된다. 남은 문자열을 순서대로 이어 붙여 새로운 문자열을 만든다.
• 새로 생긴 문자열에 폭발 문자열이 포함되어 있을 수도 있다.
• 폭발은 폭발 문자열이 문자열에 없을 때까지 계속된다.

상근이는 모든 폭발이 끝난 후에 어떤 문자열이 남는지 구해보려고 한다. 남아있는 문자가 없는 경우가 있다. 이때는 "FRULA"를 출력한다.

폭발 문자열은 같은 문자를 두 개 이상 포함하지 않는다.

입력

첫째 줄에 문자열이 주어진다. 문자열의 길이는 1보다 크거나 같고, 1,000,000보다 작거나 같다.

둘째 줄에 폭발 문자열이 주어진다. 길이는 1보다 크거나 같고, 36보다 작거나 같다.

두 문자열은 모두 알파벳 소문자와 대문자, 숫자 0, 1, ..., 9로만 이루어져 있다.

출력

첫째 줄에 모든 폭발이 끝난 후 남은 문자열을 출력한다.

풀이과정

1. 문자열들을 순차적으로 스택에 넣으면서 비교
   • 스택의 길이가 n이라고 하고, 폭발 문자열의 길이가 k라고 할때
   • 스택[n-k] ~ 스택[n]이 폭발 문자열인지 확인한다.
   • 폭발 문자열이라면, 스택에서 pop해주고 폭발에 의해 또다시 폭발 문자열 확인
   • 폭발 문자열이 아니라면, 비교과정 종료
2. 스택이 비어있다면 'FRULA', 스택에 요소가 있다면 해당 요소를 출력해주면 된다.

소스 코드

import sys
from collections import deque

input = sys.stdin.readline

string = input().rstrip()
boom = input().rstrip()

stack = deque()
for s in string:
    stack.append(s)
    while True:
        if len(stack) < len(boom):
            break
        length_s = len(stack)
        length_b = len(boom)
        flag = False
        for i in range(len(boom)):
            if boom[i] == stack[length_s-length_b+i]:
                pass
            else:
                flag = True
                break

        if flag:
            break
        else:
            for i in range(len(boom)):
                stack.pop()
if stack:
    print("".join(stack))
else:
    print("FRULA")

문제 설명

문제

백준 문제 풀이에 힘들어하는 수진이를 위해 민우는 문제해결에 도움이 되는 고무오리를 준비했다. 민우가 준비한 고무오리는 신비한 능력이 존재하는데, 최근에 풀던 백준 문제를 해결해주는 능력이다. 신비한 고무오리와 함께 수진이의 백준 풀이를 도와주자!

고무오리의 사용법은 다음과 같다.

• "고무오리 디버깅 시작" 이라고 외친다
• 문제들을 풀기 시작한다
• 고무오리를 받으면 최근 풀던 문제를 해결한다
• "고무오리 디버깅 끝" 이라고 외치면 문제풀이를 종료한다.

하지만 고무오리에는 치명적인 문제가 있는데, 풀 문제가 없는데 사용한다면 고무오리는 체벌로 두 문제를 추가한다는 점이다.

입력

첫 번째 줄에 "고무오리 디버깅 시작"이라고 주어진다. 두 번째 줄부터 "고무오리" 또는 "문제"가 주어진다. 이는 "고무오리 디버깅 끝"이 주어질 때까지 반복한다. 최대 102줄이 입력으로 주어진다.

출력

고무오리 디버깅이 끝날 때, 주어진 문제를 수진이가 해결하였는지 여부에 따라 남은 문제 없이 모든 문제를 해결하였으면 "고무오리야 사랑해"을 출력하고 하나라도 문제가 남았다면 "힝구"를 출력하라.

풀이 과정

1. 스택에 push / pop
   • 고무오리를 받은 경우 stack에서 pop
     • 이 때, 고무오리를 받았는데 stack이 비어있다면 문제 2개 push
   • 문제를 받은 경우 stack에 push
2. 디버깅 종료 이후 stack에 문제가 남아있다면 "힝구" 출력, 남아있지 않다면 "고무오리야 사랑해" 출력

소스 코드

import sys
from collections import deque

stack = deque()
while True:
    p = sys.stdin.readline().rstrip()

    if p == "고무오리 디버깅 시작":
        continue

    if p == "고무오리 디버깅 끝":
        break

    if p == "문제":
        stack.append(p)
    elif p == "고무오리":
        if len(stack) == 0:
            stack.append('문제')
            stack.append('문제')
        else:
            stack.pop()

if stack:
    print("힝구")
else:
    print("고무오리야 사랑해")