문제

난이도	번호	문제 이름
	11656	접미사 배열
	16956	늑대와 양
	17124	두 개의 배열
	1238	파티

HOW TO SOLVE

• 접미사 배열 : 단순 구현
• 늑대와 양 : 단순 구현
• 두 개의 배열 : 이진탐색 + etc ( 못 품 ㅠㅠ )
• 파티 : 다익스트라 알고리즘

접미사 배열

s = input()

suffixs = [] # 접미사 저장 리스트

# 접미사 저장
for i in range(len(s)):
    suffixs.append(s[i:])

# 출력
for suffix in sorted(suffixs):
    print(suffix)

늑대와 양

'''
- 늑대가 양이 있는 칸으로 가지 못한다 -> 1출력, 목장의 상태 출력
- 늑대가 양이 있는 칸으로 갈 수 있다 -> 0출력

-> 울타리는 아무렇게나 설치해도 되나? 
'''
r, c = map(int, input().split())

_graph = []
# 이동 방향(상, 하, 좌, 우)
dx, dy = [-1, 1, 0, 0], [0, 0, -1, 1]

for _ in range(r):
    _graph.append(list(input()))


sheeps = set() # 양의 위치
wolves = set() # 늑대의 위치

# 양과 늑대의 위치 저장
for i in range(r):
    for j in range(c):
        if _graph[i][j] == 'S': sheeps.add((i, j))
        elif _graph[i][j] == 'W': wolves.add((i, j))

# 범위 확인
def is_range(x, y):
    return 0 <= x < r and 0 <= y < c

def solve():
    # 양의 위치를 순회하면서
    for x, y in sheeps:
        for i in range(4):
            nx, ny = x + dx[i], y + dy[i] # 다음 위치
            if is_range(nx, ny) and _graph[nx][ny] == '.': # 범위에 있고 빈 곳이면
                _graph[nx][ny] = 'D' # 울타리 추가
    
    # 늑대의 위치를 순회하면서
    for x, y in wolves:
        for i in range(4):
            nx, ny = x + dx[i], y + dy[i] # 다음 위치
            if is_range(nx, ny) and _graph[nx][ny] == 'S': # 범위에 있고 양이 있으면
                return False # 실패
            
    return True # 성공

ret = solve()

# 실패라면
if not ret: print(0) # 0을 출력
# 성공이면
else:
    print(1) # 1을 출력
    
    # 목장의 상태 출력
    for i in range(r):
        for j in range(c):
            print(_graph[i][j], end='')
        print()

두 개의 배열

Not Yet 🤮

파티

'''
- 다익스트라 알고리즘을 이용하여 풀이 -> 특정 시작점에서 다른 모든 노드로 가는 최단 경로를 구해야 함
- 시작점 x라고 가정, x -> i -> x 에 걸리는 최대 시간을 구하면 됨
'''
import sys
import heapq

input = sys.stdin.readline
INF = int(1e9)

# 학생의 수=마을의 수, 간선의 개수, 파티를 열 수 있는 마을의 번호
n, m, x = map(int, input().split())

# 마을 사이의 도로 정보
graph = [[] for _ in range(n + 1)]

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

# 다익스트라
def dijkstra(s, e):
    q = []
    heapq.heappush(q, (0, s))
    dist = [INF] * (n + 1)   
    dist[s] = 0
    
    while q:
        d, cur = heapq.heappop(q)
        
        # 이미 처리된 노드
        if dist[cur] < d:
            continue
        
        # 인접 노드들에 대해
        for nxt in graph[cur]:
            cost = d + nxt[1] 
            if cost < dist[nxt[0]]: # 최단 거리 갱신
                dist[nxt[0]] = cost
                heapq.heappush(q, (cost, nxt[0]))

    return dist[e] # 시작점 -> 도착점까지 걸린 시간

_max = 0 # 가장 오래 걸리는 학생의 시간

# 각 학생들이 살고있는 마을에 대해
for s in range(1, n + 1): # 1번 마을 ~ n번 마을
    go = dijkstra(s, x) # x로 가는 시간
    come = dijkstra(x, s) # x에서 오는 시간(집으로 가는 시간)
    _max = max(_max, go + come) # 최대 시간 갱신

# 출력
print(_max)