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

문제 설명

문제

젤다의 전설 게임에서 화폐의 단위는 루피(rupee)다. 그런데 간혹 '도둑루피'라 불리는 검정색 루피도 존재하는데, 이걸 획득하면 오히려 소지한 루피가 감소하게 된다!

젤다의 전설 시리즈의 주인공, 링크는 지금 도둑루피만 가득한 N x N 크기의 동굴의 제일 왼쪽 위에 있다. [0][0]번 칸이기도 하다. 왜 이런 곳에 들어왔냐고 묻는다면 밖에서 사람들이 자꾸 "젤다의 전설에 나오는 녹색 애가 젤다지?"라고 물어봤기 때문이다. 링크가 녹색 옷을 입은 주인공이고 젤다는 그냥 잡혀있는 공주인데, 게임 타이틀에 젤다가 나와있다고 자꾸 사람들이 이렇게 착각하니까 정신병에 걸릴 위기에 놓인 것이다.

하여튼 젤다...아니 링크는 이 동굴의 반대편 출구, 제일 오른쪽 아래 칸인 [N-1][N-1]까지 이동해야 한다. 동굴의 각 칸마다 도둑루피가 있는데, 이 칸을 지나면 해당 도둑루피의 크기만큼 소지금을 잃게 된다. 링크는 잃는 금액을 최소로 하여 동굴 건너편까지 이동해야 하며, 한 번에 상하좌우 인접한 곳으로 1칸씩 이동할 수 있다.

링크가 잃을 수밖에 없는 최소 금액은 얼마일까?

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다.

각 테스트 케이스의 첫째 줄에는 동굴의 크기를 나타내는 정수 N이 주어진다. (2 ≤ N ≤ 125) N = 0인 입력이 주어지면 전체 입력이 종료된다.

이어서 N개의 줄에 걸쳐 동굴의 각 칸에 있는 도둑루피의 크기가 공백으로 구분되어 차례대로 주어진다. 도둑루피의 크기가 k면 이 칸을 지나면 k루피를 잃는다는 뜻이다. 여기서 주어지는 모든 정수는 0 이상 9 이하인 한 자리 수다.

출력

각 테스트 케이스마다 한 줄에 걸쳐 정답을 형식에 맞춰서 출력한다. 형식은 예제 출력을 참고하시오.

풀이 과정

1. 기존 다익스트라 알고리즘과는 다르게 distance를 2차원 배열로 해서 구현했던게 특이
   • 현재 좌표 기준으로 상,하,좌,우 이동하면서 거리 갱신 및 최소 히프에 이동하는 좌표 저장
   • 시작점은 [0, 0]이고, 매 순간 배열 범위를 벗어나는지 확인하는 과정 필요
2. 다익스트라 알고리즘이 종료되는 순간, distance[n-1][n-1]을 출력해주면 된다.
   • print('%d'%(변수)) 문법 사용

소스 코드

import sys
import heapq

problem_count = 1
input = sys.stdin.readline
while True:
    n = int(input().rstrip())
    if n == 0:
        break
    matrix = [list(map(int, input().rstrip().split())) for _ in range(n)]
    INT_MAX = int(10e9)
    distance =[[INT_MAX] * n for _ in range(n)]
    heap = []
    distance[0][0] = matrix[0][0]
    heapq.heappush(heap, [matrix[0][0], [0, 0]])
    dx = [-1, 1, 0, 0]
    dy = [0, 0, 1, -1]
    while heap:
        dist, pos = heapq.heappop(heap)
        if distance[pos[0]][pos[1]] < dist:
            continue
        for i in range(4):
            nx = pos[0] + dx[i]
            ny = pos[1] + dy[i]
            if 0 <= nx and nx < n and 0 <= ny and ny < n:
                if distance[nx][ny] > dist + matrix[nx][ny]:
                    distance[nx][ny] = dist + matrix[nx][ny]
                    heapq.heappush(heap, [dist + matrix[nx][ny], [nx, ny]])
    print("Problem %d: %d"%(problem_count, distance[n-1][n-1]))
    problem_count += 1

문제 설명

문제

N개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 M개의 버스가 있다. 우리는 A번째 도시에서 B번째 도시까지 가는데 드는 버스 비용을 최소화 시키려고 한다. A번째 도시에서 B번째 도시까지 가는데 드는 최소비용을 출력하여라. 도시의 번호는 1부터 N까지이다.

입력

첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 주어진다. 그리고 그 다음에는 도착지의 도시 번호가 주어지고 또 그 버스 비용이 주어진다. 버스 비용은 0보다 크거나 같고, 100,000보다 작은 정수이다.

그리고 M+3째 줄에는 우리가 구하고자 하는 구간 출발점의 도시번호와 도착점의 도시번호가 주어진다. 출발점에서 도착점을 갈 수 있는 경우만 입력으로 주어진다.

출력

첫째 줄에 출발 도시에서 도착 도시까지 가는데 드는 최소 비용을 출력한다.

풀이 과정

1. 각각의 연결 정보를 토대로 그래프 구성
2. Dijkstra 알고리즘을 활용한다.
   • 거리가 최소인 정점을 뽑아서 연결된 정점들의 거리를 갱신하는 방식
   • 최소 히프를 사용해서 매 순간 거리가 최소인 정점을 빠르게 뽑도록 한다.
3. 저장된 Distance[B]를 출력해주면 된다.

소스 코드

import sys
import heapq

input = sys.stdin.readline

N = int(input().rstrip())
M = int(input().rstrip())
graph = [[] for _ in range(N+1)]

for _ in range(M):
    fr, to, cost = map(int, input().rstrip().split())
    graph[fr].append([cost, to])

A, B = map(int, input().rstrip().split())

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

while heap:
    cost, target = heapq.heappop(heap)
    if distance[target] < cost:
        continue
    for n_cost, n_node in graph[target]:
        if distance[n_node] > cost + n_cost:
            distance[n_node] = cost + n_cost
            heapq.heappush(heap, [cost + n_cost, n_node])

print(distance[B])

문제 설명

문제

캡틴 이다솜은 자신의 해적선에 적을 공격하기 위한 대포알을 많이 보관해 놓는다. 다솜이는 미적감각이 뛰어나기 때문에, 대포알은 반드시 사면체 모양으로 쌓아놓아야 한다고 생각한다. 사면체를 만드는 방법은 길이가 N인 정삼각형 모양을 만든다. 그 위에 길이가 N-1인 정삼각형 모양을 얹고 그위에 계속 해서 얹어서 1크기의 정삼각형 모양을 얹으면 된다.

각각의 삼각형은 1, 3, 6, 10 ,..... 와 같이 대포알을 가지고 있다. 따라서 완벽하게 쌓았을 때, 한 사면체에는 1, 4, 10, 20 ,.... 개를 가지고 있을 것이다.

현재 다솜이의 해적선에 대포알이 N개가 있다. 다솜이는 영식이를 시켜서 사면체를 만들게 하고 싶다. 영식이는 물론 하기 싫지만 어쩔수 없이 다솜이가 시키는대로 사면체를 가능한 최소 개수 만큼 만들려고 한다. N개의 대포알로 만들 수 있는 사면체의 최소 개수를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 입력 N이 들어온다. N은 300,000보다 작거나 같은 자연수이다.

출력

첫째 줄에 영식이가 만들 수 있는 사면체 개수의 최솟값을 출력한다.

풀이 과정

1. 사면체가 될수있는 경우의 수를 테이블에 저장 및 DP테이블에 1로 설정한다. (최솟값이므로)
   • 즉, 경우의 수 테이블에는 [1, 4, 10, 20, ... ]이 저장된다.
   • DP[1] = 1, DP[4] = 1, DP[10] = 1, ... 이 저장된다.
2. 이후 Bottom-up 방식으로 DP테이블을 채워나가면 된다.
   • i개 대포알로 만들수 있는 최소 개수를 구할 때, 저장해 둔 경우의 수 테이블의 값들을 j라고 한다면
   • DP[i] = min(DP[i], DP[i-j[k]]) (i-j[k] > 0) 일때
3. 이후 DP[n]을 출력하면 된다.

소스 코드

import sys


N = int(sys.stdin.readline().rstrip())
curr = 1
step = 1
k = 1
area = 1
INT_MAX = int(10e9)
dp = [INT_MAX] * 300001
four = [1]
dp[1] = True
dp[0] = True
# 사면체 경우의 수 구하는 부분
while True:
    if N == area:
        print(1)
        sys.exit(0)
    if N < area:
        break
    k += 1
    curr += k
    area += curr
    four.append(area)
    if area <= 300000:
        dp[area] = 1

# dp 테이블 채우는 부분
for i in range(1, N+1):
    for j in four:
        if i - j > 0:
            dp[i] = min(dp[i], dp[i-j]+1)

print(dp[N])

문제 설명

문제

양팔 저울과 몇 개의 추가 주어졌을 때, 이를 이용하여 입력으로 주어진 구슬의 무게를 확인할 수 있는지를 결정하려고 한다.

무게가 각각 1g과 4g인 두 개의 추가 있을 경우, 주어진 구슬과 1g 추 하나를 양팔 저울의 양쪽에 각각 올려놓아 수평을 이루면 구슬의 무게는 1g이다. 또 다른 구슬이 4g인지를 확인하려면 1g 추 대신 4g 추를 올려놓으면 된다.

구슬이 3g인 경우 아래 <그림 1>과 같이 구슬과 추를 올려놓으면 양팔 저울이 수평을 이루게 된다. 따라서 각각 1g과 4g인 추가 하나씩 있을 경우 주어진 구슬이 3g인지도 확인해 볼 수 있다.

<그림 1> 구슬이 3g인지 확인하는 방법 (1은 1g인 추,4는 4g인 추, ●은 무게를 확인할 구슬)

<그림 2>와 같은 방법을 사용하면 구슬이 5g인지도 확인할 수 있다. 구슬이 2g이면 주어진 추를 가지고는 확인할 수 없다.

추들의 무게와 확인할 구슬들의 무게가 입력되었을 때, 주어진 추만을 사용하여 구슬의 무게를 확인 할 수 있는지를 결정하는 프로그램을 작성하시오.

<그림 2> 구슬이 5g인지 확인하는 방법

입력

첫째 줄에는 추의 개수가 자연수로 주어진다. 추의 개수는 30 이하이다. 둘째 줄에는 추의 무게들이 자연수로 가벼운 것부터 차례로 주어진다. 같은 무게의 추가 여러 개 있을 수도 있다. 추의 무게는 500g이하이며, 입력되는 무게들 사이에는 빈칸이 하나씩 있 다. 세 번째 줄에는 무게를 확인하고자 하는 구슬들의 개수가 주어진다. 확인할 구슬의 개수는 7이하이다. 네 번째 줄에는 확인하고자 하는 구슬들의 무게가 자연수로 주어지며, 입력되는 무게들 사이에는 빈 칸이 하나씩 있다. 확인하고자 하는 구슬의 무게는 40,000보다 작거나 같은 자연수이다.

출력

주어진 각 구슬의 무게에 대하여 확인이 가능하면 Y, 아니면 N 을 차례로 출력한다. 출력은 한 개의 줄로 이루어지며, 각 구슬에 대한 답 사이에는 빈칸을 하나씩 둔다.

풀이 과정

1. 추를 오름차순으로 두면서, 각각의 추를 둘 때 가능한 경우의 수는 3가지이다.
   • 추를 왼쪽에 둘 때
   • 추를 오른쪽에 둘 때
   • 현재 추만 오른쪽에 두고 왼쪽에 추를 모두 두었을 때
2. 따라서, 위의 3가지 경우의 수로 DP를 구성하면 된다.
3. 마지막으로 각각의 구슬에 대해, 확인 가능 여부를 출력해주면 된다.

소스 코드

import sys

input = sys.stdin.readline

weights_count = int(input().rstrip())
weights = list(map(int, input().rstrip().split()))

marbles_count = int(input().rstrip())
marbles = list(map(int, input().rstrip().split()))

dp = [False] * 40001
dp[0] = True

for weight in weights:
    canmake = set()
    for i in range(40001):
        if dp[i] == True:
            if i + weight <= 40001:
                canmake.add(i+weight) # 오른쪽에 놓았을때,
            if i - weight >= 0:
                canmake.add(i-weight) # 왼쪽에 놓았을 때
            if weight - i >= 0:
                canmake.add(weight-i) # 현재 물체만 오른쪽에 두고 나머지는 왼쪽에 두었을 때
    for c in canmake:
        dp[c] = True

for marble in marbles:
    if dp[marble] == True:
        print('Y', end=" ")
    else:
        print('N', end=" ")

문제 설명

문제

그래프의 정점의 집합을 둘로 분할하여, 각 집합에 속한 정점끼리는 서로 인접하지 않도록 분할할 수 있을 때, 그러한 그래프를 특별히 이분 그래프 (Bipartite Graph) 라 부른다.

그래프가 입력으로 주어졌을 때, 이 그래프가 이분 그래프인지 아닌지 판별하는 프로그램을 작성하시오.

입력

입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K(2≤K≤5)가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V(1≤V≤20,000)와 간선의 개수 E(1≤E≤200,000)가 빈 칸을 사이에 두고 순서대로 주어진다. 각 정점에는 1부터 V까지 차례로 번호가 붙어 있다. 이어서 둘째 줄부터 E개의 줄에 걸쳐 간선에 대한 정보가 주어지는데, 각 줄에 인접한 두 정점의 번호가 빈 칸을 사이에 두고 주어진다.

출력

K개의 줄에 걸쳐 입력으로 주어진 그래프가 이분 그래프이면 YES, 아니면 NO를 순서대로 출력한다.

풀이 과정

• 문제만으론 정확히 어떤 경우에 이분 그래프인지 몰라서 더 찾아보았다.

• 요약해 보면, 색이 0과 1이 있고, a-b가 연결되어 있을때 a와 b의 색이 다르다 보면 된다.

1. bfs를 활용한다.
   1. 현재 색이 0일때, 인접한 노드의 색을 1로 한다.
   2. 현재 색이 1일때, 인접한 노드의 색을 0으로 한다.
2. bfs 진행 도중에 현재 색과 인접한 노드의 색이 같은 경우에는 이분 그래프가 되지 않는다.
3. 전체 정점에 대해서 이분 그래프인 경우에는 True, 아닌 경우에는 False를 리턴한다.

소스 코드

import sys
from collections import deque

input = sys.stdin.readline

K = int(input().rstrip())

def bfs(graph, visited, start):
    visited[start] = 0 # 시작 색은 0
    queue = deque([[start, 0]])
    while queue:
        e, v = queue.popleft() # 현재 색깔
        value = 1 if v == 0 else 0 # 현재 색깔 전환
        for next_edge in graph[e]:
            if visited[next_edge] == -1:
                queue.append([next_edge, value])
                visited[next_edge] = value
            elif visited[next_edge] == v: # 다음 엣지의 색이 현재 색과 같으면 실패
                return False
    return True # 시작 정점에 대한 bfs 성공


for _ in range(K):
    V, E = map(int, input().rstrip().split())
    graph = [[] for _ in range(V+1)]
    for __ in range(E):
        a, b = map(int, input().rstrip().split())
        graph[a].append(b)
        graph[b].append(a)
    visited = [-1] * (V+1)

    answer = True
    for i in range(1, V+1):
        if visited[i] == -1:
            if not bfs(graph, visited, i):
                answer = False
                break

    if answer:
        print("YES")
    else:
        print("NO")

문제 설명

문제

몇 개의 자연수로 이루어진 두 집합 A와 B가 있다. 집합 A에는 속하면서 집합 B에는 속하지 않는 모든 원소를 구하는 프로그램을 작성하시오.

입력

첫째 줄에는 집합 A의 원소의 개수 n(A)와 집합 B의 원소의 개수 n(B)가 빈 칸을 사이에 두고 주어진다. (1 ≤ n(A), n(B) ≤ 500,000)이 주어진다. 둘째 줄에는 집합 A의 원소가, 셋째 줄에는 집합 B의 원소가 빈 칸을 사이에 두고 주어진다. 하나의 집합의 원소는 2,147,483,647 이하의 자연수이며, 하나의 집합에 속하는 모든 원소의 값은 다르다.

출력

첫째 줄에 집합 A에는 속하면서 집합 B에는 속하지 않는 원소의 개수를 출력한다. 다음 줄에는 구체적인 원소를 빈 칸을 사이에 두고 증가하는 순서로 출력한다. 집합 A에는 속하면서 집합 B에는 속하지 않는 원소가 없다면 첫째 줄에 0만을 출력하면 된다.

풀이 과정

• 이진 탐색 문제로도 풀 수 있음. B를 정렬한 후, A의 각 원소를 B에서 이진탐색으로 구현하면 될듯?
• Set의 in연산자를 쓰면 빠르게 해결할 수 있음.

1. A의 원소를 정렬한다. (오름차순으로 출력해야 하므로)
2. B를 Set 자료구조로 바꾼다. (찾을때 리스트보다 훨씬 빠름, 또한 중복되는 원소가 없으므로)
3. A의 각 원소가 B에 존재하는지 확인한다.
   • 있으면 따로 리스트에 저장해 둔다.
4. 리스트의 길이와 리스트의 요소들을 출력해주면 된다
   • python에서 * 쓰면 쉽게 리스트의 요소들 출력 가능(" ".join한것과 같음)

소스 코드

import sys


nA, nB = map(int,sys.stdin.readline().rstrip().split())
A = list(map(int, sys.stdin.readline().rstrip().split()))
B = list(map(int, sys.stdin.readline().rstrip().split()))

A.sort()
B = set(B)
answer = []

for a in A:
    if a not in B:
        answer.append(a)

print(len(answer))
if answer:
    print(*answer)

문제

문제

수식은 일반적으로 3가지 표기법으로 표현할 수 있다. 연산자가 피연산자 가운데 위치하는 중위 표기법(일반적으로 우리가 쓰는 방법이다), 연산자가 피연산자 앞에 위치하는 전위 표기법(prefix notation), 연산자가 피연산자 뒤에 위치하는 후위 표기법(postfix notation)이 그것이다. 예를 들어 중위 표기법으로 표현된 a+b는 전위 표기법으로는 +ab이고, 후위 표기법으로는 ab+가 된다.

이 문제에서 우리가 다룰 표기법은 후위 표기법이다. 후위 표기법은 위에서 말한 법과 같이 연산자가 피연산자 뒤에 위치하는 방법이다. 이 방법의 장점은 다음과 같다. 우리가 흔히 쓰는 중위 표기식 같은 경우에는 덧셈과 곱셈의 우선순위에 차이가 있어 왼쪽부터 차례로 계산할 수 없지만 후위 표기식을 사용하면 순서를 적절히 조절하여 순서를 정해줄 수 있다. 또한 같은 방법으로 괄호 등도 필요 없게 된다. 예를 들어 a+b*c를 후위 표기식으로 바꾸면 abc*+가 된다.

중위 표기식을 후위 표기식으로 바꾸는 방법을 간단히 설명하면 이렇다. 우선 주어진 중위 표기식을 연산자의 우선순위에 따라 괄호로 묶어준다. 그런 다음에 괄호 안의 연산자를 괄호의 오른쪽으로 옮겨주면 된다.

예를 들어 a+b*c는 (a+(b*c))의 식과 같게 된다. 그 다음에 안에 있는 괄호의 연산자 *를 괄호 밖으로 꺼내게 되면 (a+bc*)가 된다. 마지막으로 또 +를 괄호의 오른쪽으로 고치면 abc*+가 되게 된다.

다른 예를 들어 그림으로 표현하면 A+B*C-D/E를 완전하게 괄호로 묶고 연산자를 이동시킬 장소를 표시하면 다음과 같이 된다.

이러한 사실을 알고 중위 표기식이 주어졌을 때 후위 표기식으로 고치는 프로그램을 작성하시오

입력

첫째 줄에 중위 표기식이 주어진다. 단 이 수식의 피연산자는 A~Z의 문자로 이루어지며 수식에서 한 번씩만 등장한다. 그리고 -A+B와 같이 -가 가장 앞에 오거나 AB와 같이 *가 생략되는 등의 수식은 주어지지 않는다. 표기식은 알파벳 대문자와 +, -, *, /, (, )로만 이루어져 있으며, 길이는 100을 넘지 않는다.

출력

첫째 줄에 후위 표기식으로 바뀐 식을 출력하시오

풀이과정

1. 식을 순차적으로 한자리씩 방문한다.
2. A, B, C등 피연산자는 그대로 출력해준다.
3. 연산자일 때는 스택에 넣어준다.
   • +, - 연산자일때는 괄호('(')를 만나기 전까지 스택에서 모두 빼주고 넣음(곱하기나 나눗셈보다는 우선순위가 낮고, 덧셈, 뺄셈과는 동등)
   • *, / 연산자 일때는 괄호를 만나기 전까지 스택에서 *과 /를 빼주고 넣는다.(덧셈, 뺄셈보다 우선순위가 높으므로 덧셈,뺄셈 위에 있을 수 있음, 곱하기와 나눗셈은 우선순위가 동등하므로 빼줌)
   • '(' 일때는 그냥 넣어도 되지만, ')'일때는 '('를 만날 때까지 스택에서 연산자들을 빼준다.
   • 맨 마지막에는 스택이 빌때까지 모두 빼준다.
4. 피연산자는 그냥 문자열에 붙여주고, 연산자같은 경우는 pop될때마다 붙여주면 된다.

소스 코드

import sys

t = sys.stdin.readline().rstrip()

op_stack = []
answer = ''
p = ['+', '-', '*', '/', '(', ')']
for s in t:
    if s not in p:
        answer += s
    elif s == '+' or s == '-':
        while op_stack:
            if op_stack[-1] != '(':
                answer += op_stack.pop()
            else:
                break
        op_stack.append(s)
    elif s == '*' or s == '/':
        while op_stack:
            if op_stack[-1] == '*' or op_stack[-1] == '/':
                answer += op_stack.pop()
            else:
                break
        op_stack.append(s)
    elif s == ')':
        while op_stack:
            if op_stack[-1] != '(':
                answer += op_stack.pop()
            else:
                op_stack.pop()
                break
    else:
        op_stack.append(s)

while op_stack:
    answer += op_stack.pop()

print(answer)

문제 설명

문제

지훈이는 미로에서 일을 한다. 지훈이를 미로에서 탈출하도록 도와주자!

미로에서의 지훈이의 위치와 불이 붙은 위치를 감안해서 지훈이가 불에 타기전에 탈출할 수 있는지의 여부, 그리고 얼마나 빨리 탈출할 수 있는지를 결정해야한다.

지훈이와 불은 매 분마다 한칸씩 수평또는 수직으로(비스듬하게 이동하지 않는다) 이동한다.

불은 각 지점에서 네 방향으로 확산된다.

지훈이는 미로의 가장자리에 접한 공간에서 탈출할 수 있다.

지훈이와 불은 벽이 있는 공간은 통과하지 못한다.

입력

입력의 첫째 줄에는 공백으로 구분된 두 정수 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1000 이다. R은 미로 행의 개수, C는 열의 개수이다.

다음 입력으로 R줄동안 각각의 미로 행이 주어진다.

각각의 문자들은 다음을 뜻한다.

• #: 벽
• .: 지나갈 수 있는 공간
• J: 지훈이의 미로에서의 초기위치 (지나갈 수 있는 공간)
• F: 불이 난 공간

J는 입력에서 하나만 주어진다.

출력

지훈이가 불이 도달하기 전에 미로를 탈출 할 수 없는 경우 IMPOSSIBLE 을 출력한다.

지훈이가 미로를 탈출할 수 있는 경우에는 가장 빠른 탈출시간을 출력한다.

풀이 과정

• 전체적으로 소스가 길어지는 문제인거 같음..

1. 현재 지훈이의 위치를 큐에 넣어준다.
2. 현재 불의 위치를 구해 준다.
3. bfs를 활용하여 큐의 맨 앞에서부터 위치를 빼주면서 지훈이가 갈수있는 위치를 큐에 넣어준다.
   • 이 과정을 하다 보면 이동 횟수가 바뀌는 시점이 존재한다.
   • 이동 횟수가 바뀌는 시점에 bfs를 통해 불을 확산시킨다, 이 때, 매 순간 반복문으로 불의 위치를 찾으면 시간 초과가 난다.
   • 따라서.. 한번 확산시키면서, 확산된 불의 위치 또한 큐에 저장해두어야 한다.
4. 배열의 범위를 넘게되는 순간 탈출한 것이므로 그때의 이동 횟수를 출력하고 종료한다.
5. 만약 (4)를 실행하지 않고 큐의 요소가 비게 되면 탈출이 불가능한 것이므로 IMPOSSIBLE을 출력해 준다.

• 소스가 조금 복잡하게 짜여 있음.

import sys
from collections import deque

input = sys.stdin.readline

# 불 확산 함수
Fire = deque()
def spread(matrix, R, C):
    global Fire
    stop_flag = 0
    if Fire:
        stop_flag = Fire[0][2]

    dx = [-1, 1, 0, 0]
    dy = [0, 0, 1, -1]
    while Fire:
        if Fire[0][2] > stop_flag:
            break
        cx, cy, step = Fire.popleft()
        for i in range(4):
            nx = cx + dx[i]
            ny = cy + dy[i]
            if 0 <= nx and nx < R and 0 <= ny and ny < C:
                if matrix[nx][ny] == '.' or matrix[nx][ny] == 'J':
                    matrix[nx][ny] = 'F'
                    Fire.append([nx, ny, step+1])


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

for i in range(R):
    for j in range(C):
        if matrix[i][j] == 'F':
            Fire.append([i, j, 0])

J_x, J_y = 0, 0
flag = False
# 지훈이의 위치 찾음
for i in range(R):
    for j in range(C):
        if matrix[i][j] == 'J':
            J_x, J_y = i, j
            flag = True
            break
    if flag:
        break


Jh_queue = deque([[J_x, J_y, 0]])
visited = set()
dx = [-1, 1, 0, 0]
dy = [0, 0, 1, -1]
last = 0
visited.add((J_x, J_y))
answer_flag = False
answer = 0
while Jh_queue:
    jx, jy, movement_count = Jh_queue.popleft()
    # 이동 횟수가 늘어나면 불 확산
    if last != movement_count:
        spread(matrix, R, C)
        last = movement_count

    # 현재 방문하려는 위치에 이미 불 퍼진 상태면 스킵
    if matrix[jx][jy] == 'F':
        continue

    for i in range(4):
        nx, ny = jx + dx[i], jy + dy[i]
        if 0 <= nx and nx < R and 0 <= ny and ny < C:
            if matrix[nx][ny] == '.' and (nx, ny) not in visited:
                Jh_queue.append([nx, ny, movement_count+1])
                visited.add((nx, ny))
        elif 0 > nx or nx >= R or 0 > ny or ny >= C:
            answer_flag = True
            answer = movement_count + 1
            break
    if answer_flag:
        break

if answer_flag:
    print(answer)
else:
    print("IMPOSSIBLE")

문제 설명

문제

다음과 같이 정의된 수열이 있다.

• D[1] = A
• D[n] = D[n-1]의 각 자리의 숫자를 P번 곱한 수들의 합

예를 들어 A=57, P=2일 때, 수열 D는 {57, 74(=5^2+7^2=25+49), 65, 61, 37, 58, 89, 145, 42, 20, 4, 16, 37, …}이 된다. 그 뒤에는 앞서 나온 수들(57부터가 아니라 58부터)이 반복된다.

이와 같은 수열을 계속 구하다 보면 언젠가 이와 같은 반복수열이 된다. 이때, 반복되는 부분을 제외했을 때, 수열에 남게 되는 수들의 개수를 구하는 프로그램을 작성하시오. 위의 예에서는 {57, 74, 65, 61}의 네 개의 수가 남게 된다.

입력

첫째 줄에 A(1 ≤ A ≤ 9999), P(1 ≤ P ≤ 5)가 주어진다.

출력

첫째 줄에 반복되는 부분을 제외했을 때, 수열에 남게 되는 수들의 개수를 출력한다.

풀이 과정

1. set에 반복되는 요소가 나올때까지 수열을 넣는다
   • 반복되는 요소가 나온다면 해당 요소의 값을 따로 저장만 하고 넣지는 않음.
2. 반복되는 요소에서부터 set에서 나오지 않을때까지 수열을 구하고 해당 수열을 set에서 빼준다.
3. set에 남아있는 수열이 즉, 반복되는 부분이 제외된 수열이다.

소스 코드

import sys
input = sys.stdin.readline

A, P = map(int, input().rstrip().split())

def get_next(n, p):
    nvalue = 0
    while n > 0:
        nvalue += (n % 10) ** p
        n = n // 10
    return nvalue

visited = set()

current = A
dup_start = 0
# 1. 지나간 숫자중에 하나가 다시 나타나는 경우 중복의 시작
while True:
    if current not in visited:
        visited.add(current)
    else:
        dup_start = current
        break
    current = get_next(current, P)

# 2. 중복 시작점에서 중복 끝날때까지 요소들 빼줌
while dup_start in visited:
    visited.remove(dup_start)
    dup_start = get_next(dup_start, P)

# 3. 남아있는 요소의 개수 출력
print(len(visited))

문제 설명

문제

1부터 N까지 정수 N개로 이루어진 순열을 나타내는 방법은 여러 가지가 있다. 예를 들어, 8개의 수로 이루어진 순열 (3, 2, 7, 8, 1, 4, 5, 6)을 배열을 이용해 표현하면

(1 2 3 4 5 6 7 8

3 2 7 8 1 4 5 6) 와 같다. 또는, Figure 1과 같이 방향 그래프로 나타낼 수도 있다.

              순열을 배열을 이용해 (1…i…n  π1…πi…πn) 로 나타냈다면, i에서 πi로 간선을 이어 그래프로 만들 수 있다.

Figure 1에 나와있는 것 처럼, 순열 그래프 (3, 2, 7, 8, 1, 4, 5, 6) 에는 총 3개의 사이클이 있다. 이러한 사이클을 "순열 사이클" 이라고 한다.

N개의 정수로 이루어진 순열이 주어졌을 때, 순열 사이클의 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 순열의 크기 N (2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 순열이 주어지며, 각 정수는 공백으로 구분되어 있다.

출력

각 테스트 케이스마다, 입력으로 주어진 순열에 존재하는 순열 사이클의 개수를 출력한다.

풀이 과정

0. 그래프로 보면.. 1번 노드가 3번 노드와 연결되어 있다 이런식으로 해석 가능
1. 노드 1~n번째 각각에서 연결된 노드가 사이클을 형성할때까지 이동해본다.
   • dfs 사용
   • 끝나는 조건 : 이동할 때 시작 숫자 = 순열[index]
2. visited를 두어 방문했던 노드들을 다시 방문하지 않도록 처리한다.

소스 코드

import sys

input = sys.stdin.readline

T = int(input().rstrip())

def dfs(visited, sequence, start, current):
    if visited[current] == True:
        return False
    visited[current] = True
    if current == start:
        return True
    return dfs(visited, sequence, start, sequence[current])

for _ in range(T):
    N = int(input().rstrip())
    sequence = [0] + list(map(int, input().rstrip().split()))
    visited = [False] * (N+1)
    answer = 0
    for i in range(1, N+1):
        if visited[i] == False:
            answer += 1
            dfs(visited, sequence, i, sequence[i])
    print(answer)