Q.15 특정 거리의 도시 찾기
난이도: 🌕🌗
풀이시간: 30분
시간제한: 2초
메모리제한: 256MB
기출: 핵심 유형
링크: https://www.acmicpc.net/problem/18352
어떤 나라에는 1~N번까지의 도시와 M개의 단방향 도로가 존재한다. 모든 도로의 거리는 1이다. 이때 특정한 도시 X로부터 출발하여 도달할 수 있는 모든 도시 중에서, 최단 거리가 정확히 K인 모든 도시의 번호를 출력하는 프로그램을 작성하시오. 또한 출발 도시 X에서 출발 도시 X로 가는 최단 거리는 항상 0이라고 가정한다.
입력 조건
- 첫째 줄에 도시의 개수 N, 도로의 개수 M, 거리 정보 K, 출발 도시의 번호 X가 주어진다. (2≤N≤300,000, 1≤M≤1,000,000, 1≤K≤300,000, 1≤X≤N)
- 둘째 줄부터 M개의 줄에 걸쳐서 두 개의 자연수 A,B가 주어지며, 각 자연수는 공백으로 구분한다.
- 이는 A번 도시에서 B번 도시로 이동하는 단방향 도로가 존재한다는 의미이다. (1≤A,B≤N) 단, A와 B는 서로 다른 자연수이다.
출력 조건
- X로부터 출발하여 도달할 수 있는 도시 중에서, 최단 거리가 K인 모든 도시의 번호를 한 줄에 하나씩 오름차순으로 출력한다.
- 이때 도달할 수 있는 도시 중에서, 최단 거리가 K인 도시가 하나도 존재하지 않으면 -1을 출력한다.
# 입력예시1
4 4 2 1
1 2
1 3
2 3
2 4
# 출력예시1
4
# 입력예시2
4 3 2 1
1 2
1 3
1 4
# 출력예시2
-1
# 입력예시3
4 4 1 1
1 2
1 3
2 3
2 4
# 출력예시3
2
3<내가 푼 방식>
graph[][x] graph[x][y] graph[y][]
위와 같이 연쇄적으로 도로를 찾아서 거리를 1씩 증가시키려고 했는데 코드가 잘 나오지 않는다...
<해설>
📌그래프에서 모든 간선의 비용이 동일할 때는 BFS를 이용하여 최단 거리를 찾을 수 있다.
노드의 개수 N은 최대 300,000이며 간선의 개수 M은 최대 1,000,000개 → 시간복잡도 O(N+M)인 BFS 사용 가능
먼저 특정한 도시 X를 시작점으로 BFS를 수행하여 모든 도시까지의 최단 거리를 계산한 뒤에, 각 최단 거리를 하나씩 확인하며 그 값이 K인 경우에 해당 도시의 번호를 출력하면 된다.
from collections import deque
# 도시의 개수, 도로의 개수, 거리 정보, 출발 도시 번호
n, m, k, x = map(int, input().split())
graph = [[] for _ in range(n + 1)]
# 모든 도로 정보 입력 받기
for _ in range(m):
a, b = map(int, input().split())
graph[a].append(b)
# 모든 도시에 대한 최단 거리 초기화
distance = [-1] * (n + 1)
distance[x] = 0 # 출발 도시까지의 거리는 0으로 설정
# 너비 우선 탐색(BFS) 수행
q = deque([x])
while q:
now = q.popleft()
# 현재 도시에서 이동할 수 있는 모든 도시를 확인
for next_node in graph[now]:
# 아직 방문하지 않은 도시라면
if distance[next_node] == -1:
# 최단 거리 갱신
distance[next_node] = distance[now] + 1
q.append(next_node)
# 최단 거리가 K인 모든 도시의 번호를 오름차순으로 출력
check = False
for i in range(1, n + 1):
if distance[i] == k:
print(i)
check = True
# 만약 최단 거리가 K인 도시가 없다면, -1 출력
if check == False:
print(-1)Q16. 연구소
난이도: ⭐⭐
풀이시간: 40분
시간제한: 2초
메모리제한: 512MB
기출: 삼성전자 SW 역량테스트
링크: https://www.acmicpc.net/problem/14502
연구소는 크기가 N x M인 직사각형으로 나타낼 수 있으며, 직사각형은 1x1 크기의 정사각형으로 나누어져 있다. 연구소는 빈칸, 벽으로 이루어져 있으며, 벽은 칸 하나를 가득 차지합니다.
일부 칸은 바이러스가 존재하며, 이 바이러스는 상하좌우로 인접한 빈칸으로 모두 퍼져나갈 수 있습니다. 새로 세울 수 있는 벽의 개수는 3개이며, 꼭 3개를 세워야 합니다.
연구소의 지도가 주어졌을 때 얻을 수 있는 안전 영역 크기의 최댓값을 구하는 프로그램을 작성하시오.
입력 조건
- 첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. (3≤N, M≤8)
- 둘째 줄부터 N개의 줄에 지도의 모양이 주어집니다. 0은 빈칸, 1은 벽, 2는 바이러스가 있는 위치이다. 2의 개수는 2보다 크거나 같고, 10보다 작거나 같은 자연수이다.
- 빈칸의 개수는 3개 이상이다.
출력 조건
- 첫째 줄에 얻을 수 있는 안전 영역의 최대 크기를 출력한다.
# 입력예시1
7 7
2 0 0 0 1 1 0
0 0 1 0 1 2 0
0 1 1 0 1 0 0
0 1 0 0 0 0 0
0 0 0 0 0 1 1
0 1 0 0 0 0 0
0 1 0 0 0 0 0
# 출력예시1
27
# 입력예시2
4 6
0 0 0 0 0 0
1 0 0 0 0 2
1 1 1 0 0 2
0 0 0 0 0 2
# 출력예시2
9
# 입력예시3
8 8
2 0 0 0 0 0 0 2
2 0 0 0 0 0 0 2
2 0 0 0 0 0 0 2
2 0 0 0 0 0 0 2
2 0 0 0 0 0 0 2
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
# 출력예시3
3<내가 푼 방식>
안전 영역 크기가 최대가 되게 하는 벽 3개의 위치를 어떻게 정해야 하는지 잘 모르겠다...🥲
n, m = map(int, input().split())
lab_map = [[] for _ in range(n + 1)]
for i in range(1, n + 1):
lab_map[i] = list(map(int, input().split()))
for i in range(1, n + 1):
for j in range(1, m + 1):
if lab_map[i][j] == 2:<해설>
벽을 3개 설치하는 모든 경우의 수를 다 계산해야 한다.
전체 맵의 크기가 8x8이므로, 벽을 설치할 수 있는 모든 조합의 수는 최악의 경우 (바이러스가 하나도 존재하지 않는 경우) 64_C_3
이는 100,000보다 작은 수이므로, 모든 경우의 수를 고려해도 제한 시간 안에 문제를 해결 가능!
모든 조합을 계산할 때는 파이썬의 조합 라이브러리를 이용하거나, DFS/BFS를 이용하여 해결 가능!
➡️ 벽의 개수가 3개가 되는 모든 조합을 찾은 뒤에 그러한 조합에 대해서 안전 영역의 크기를 계산하면 된다.안전 영역의 크기를 구하는 것 또한 DFS/BFS를 이용해 계산 가능!
정리하면, 초기에 비어 있는 모든 공간 중에서 3개를 골라 벽을 설치한다.
매번 벽을 설치할 때마다, 각 바이러스가 사방으로 퍼지는 것을 DFS/BFS로 계산하여 안전 영역을 구해야 한다.
n, m = map(int, input().split())
data = [] # 초기 맵 리스트
temp = [[0] * m for _ in range(n)] # 벽을 설치한 뒤의 맵 리스트
for _ in range(n):
data.append(list(map(int, input().split())))
# 4가지 이동 방향에 대한 리스트
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]
result = 0
# 깊이 우선 탐색(DFS)을 이용해 각 바이러스가 사방으로 퍼지도록 하기
def virus(x, y):
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
# 상, 하, 좌, 우 중에서 바이러스가 퍼질 수 있는 경우
if nx >= 0 and nx < n and ny >= 0 and ny < m:
if temp[nx][ny] == 0:
# 해당 위치에 바이러스 배치하고, 다시 재귀적으로 수행
temp[nx][ny] = 2
virus(nx, ny)
# 현재 맵에서 안전 영역의 크기 계산하는 메서드
def get_score():
score = 0
for i in range(n):
for j in range(m):
if temp[i][j] == 0:
score += 1
return score
# 깊이 우선 탐색(DFS)을 이용해 울타리를 설치하면서, 매 번 안전 영역의 크기 계산
def dfs(count):
global result
# 울타리가 3개 설치된 경우
if count == 3:
for i in range(n):
for j in range(m):
temp[i][j] = data[i][j]
# 각 바이러스의 위치에서 전파 진행
for i in range(n):
for j in range(m):
if temp[i][j] == 2:
virus(i, j)
# 안전 영역의 최대값 계산
result = max(result, get_score())
return
# 빈 공간에 울타리를 설치
for i in range(n):
for j in range(m):
if data[i][j] == 0:
data[i][j] = 1
count += 1
dfs(count)
data[i][j] = 0
count -= 1
dfs(0)
print(result)Q17. 경쟁적 전염
난이도: ⭐⭐
풀이시간: 50분
시간제한: 1초
메모리제한: 256MB
기출: 핵심 유형
링크: https://www.acmicpc.net/problem/18405
N x N 크기의 시험관이 있다. 시험관은 1x1 크기의 칸으로 나누어지며, 특정한 위치에는 바이러스가 존재할 수 있다. 모든 바이러스는 1번부터 K번까지의 바이러스 종류 중 하나.
시험관에 존재하는 모든 바이러스는 1초마다 상,하,좌,우로 증식. 단, 매 초마다 번호가 낮은 종류의 바이러스부터 먼저 증식. 증식 과정에서 특정한 칸에 이미 어떠한 바이러스가 존재하면, 그 곳에는 다른 바이러스가 들어갈 수 없다.
시험관의 크기와 바이러스의 위치 정보가 주어졌을 때, S초가 지난 후에 (X,Y)에 존재하는 바이러스의 종류를 출력하는 프로그램을 작성하시오.
만약 S초가 지난 후에 해당 위치에 바이러스가 존재하지 않는다면, 0을 출력한다. 이때 X와 Y는 행과 열의 위치를 의미하며, 시험관의 가장 왼쪽 위에 해당하는 곳은 (1,1)에 해당.
입력 조건
- 첫째 줄에 자연수 N, K가 공백을 기준으로 구분
(1 ≤ N ≤ 200, 1 ≤ K ≤ 1,000) - 둘째 줄부터 N개의 줄에 걸쳐 시험관의 정보
- 각 행은 N개의 원소로 구성되며, 해당 위치에 존재하는 바이러스의 번호가 공백을 기준으로 구분
단, 해당 위치에 바이러스가 존재하지 않는 경우 0 - 모든 바이러스의 번호는 K 이하의 자연수만
- 각 행은 N개의 원소로 구성되며, 해당 위치에 존재하는 바이러스의 번호가 공백을 기준으로 구분
- N+2번째 줄에는 S, X, Y가 공백을 기준으로 구분
(0 ≤ S ≤ 10,000, 1 ≤ X, Y ≤ N)
출력 조건
- S초 뒤에 (X,Y)에 존재하는 바이러스의 종류를 출력
- 만약 S초 뒤ㅇ에 해당 위치에 바이러스가 존재하지 않는다면, 0 출력
# 입력예시 1
3 3
1 0 2
0 0 0
3 0 0
2 3 2
# 출력예시 1
3
# 입력예시 2
3 3
1 0 2
0 0 0
3 0 0
1 2 2
# 출력예시 2
0<해설>
너비 우선 탐색(DFS)으로 해결!
각 바이러스가 낮은 번호부터 증식하므로, 초기에 큐에 원소를 삽입할 때는 낮은 바이러스의 번호부터 삽입해야 한다.
이후에 너비 우선 탐색을 수행하며 방문하지 않은 위치를 차례대로 방문하도록 하면 된다.
from collections import deque
n, k = map(int, input().split())
graph = [] # 전체 보드 정보를 담는 리스트
data = [] # 바이러스에 대한 정보를 담는 리스트
for i in range(n):
# 보드 정보를 한 줄 단위로 입력
graph.append(list(map(int, input().split())))
for j in range(n):
# 해당 위치에 바이러스가 존재하는 경우
if graph[i][j] != 0:
# (바이러스 종류, 시간, 위치 X, 위치 Y) 삽입
data.append((graph[i][j], 0, i, j))
# 정렬 이후에 큐로 옮기기 (낮은 번호의 바이러스가 먼저 증식하므로)
data.sort()
q = deque(data)
target_s, target_x, target_y = map(int, input().split())
# 바이러스가 퍼져나갈 수 있는 4가지의 위치
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]
# 너비 우선 탐색(BFS) 진행
while q:
virus, s, x, y = q.popleft()
# 정확히 s초가 지나거나, 큐가 빌 때까지 반복
if s == target_s:
break
# 현재 노드에서 주변 4가지 위치를 각각 확인
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
# 해당 위치로 이동할 수 있는 경우
if 0 <= nx and nx < n and 0 <= ny and ny < n:
# 아직 방문하지 않은 위치라면, 그 위치에 바이러스 넣기
if graph[nx][ny] == 0:
graph[nx][ny] = virus
q.append((virus, s + 1, nx, ny))
print(graph[target_x - 1][target_y - 1])Q18. 괄호 변환
난이도: ⭐
풀이시간: 20분
시간제한: 1초
메모리제한: 128MB
기출: 2020 카카오 신입 공채 1차
링크: https://programmers.co.kr/learn/courses/30/lessons/60058
'('와 ')'로만 이루어진 문자열이 있을 때,
- 균형잡힌 괄호 문자열: '('의 개수와 ')'의 개수가 같을 경우
- 올바른 괄호 문자열: 균형잡힌 괄호 문자열이면서 '('와 ')'의 괄호의 짝도 모두 맞을 경우
'('와 ')'로만 이루어진 문자열 w가 "균형잡힌 괄호 문자열"이라면 다음과 같은 과정을 통해 올바른 괄호 문자열로 변환 가능
-
입력이 빈 문자열인 경우, 빈 문자열 반환
-
문자열 w를 두 "균형잡힌 괄호 문자열" u, v로 분리.
단, u는 "균형잡힌 괄호 문자열"로 더 이상 분리할 수 없어야 하며, v는 빈 문자열이 될 수 있다. -
수행한 결과 문자열을 u에 이어 붙인 후 반환
- 문자열 u가 "올바른 괄호 문자열"이라면 문자열 v에 대해 1단계부터 다시 수행
-
문자열 u가 "올바른 괄호 문자열"이 아니라면 아래 과정을 수행
- 4-1. 빈 문자열에 첫 번째 문자로 '('를 붙인다.
- 4-2. 문자열 v에 대해 1단계부터 재귀적으로 수행한 결과 문자열을 이어 붙인다.
- 4-3. ')'를 다시 붙인다.
- 4-4. u의 첫 번째와 마지막 문자를 제거하고, 나머지 문자열의 괄호 방향을 뒤집어서 뒤에 붙인다.
- 4-5. 생성된 문자열 반환
"균형잡힌 괄호 문자열" p가 매개변수로 주어질 때, 주어진 알고리즘을 수행해 "올바른 괄호 문자열"로 변환한 결과를 return 하도록 solution 함수를 완성하시오.
매개변수 설명
- p는 '('와 ')'로만 이루어진 문자열이며 길이는 2 이상 1,000 이하인 짝수
- 문자열 p를 이루는 '('와 ')'의 개수는 항상 같다.
- 만약 p가 이미 올바른 괄호 문자열이라면 그대로 return
기본 코드
def solution(p):
answer = ''
return answer<내가 푼 방식>
잘못 푼 것 같다!
def solution(p):
answer = ''
p = len(p)
cnt_left = 0 # '(' 개수
cnt_right = 0 # ')' 개수
idx = 0 # u, v로 분리하는 기준이 되는 index 위치
if len(p) == 0:
return answer
for i in range(len(p)):
if p[i] == '(':
cnt_left += 1
else:
cnt_right += 1
if cnt_left == cnt_right: # 처음으로 균형잡힌 괄호 문자열이 될 때의 index 찾기
idx = cnt_left + cnt_right
break
u = p[:idx+1]
v = p[idx+1:]
temp = []
temp_left = 0
temp_right = 0
is_u_right = True
if u[0] == '(':
temp.append(u[0])
temp_left += 1
for i in range(1, len(u)):
if u[i] == '(':
temp_left += 1
else:
temp_right += 1
if temp_left < temp_right: # u가 "올바른 괄호 문자열"이 아닐 때
is_u_right = False
break
temp.append(u[i])
if is_u_right:
# ...............................
return answer<해설>
엄밀히 말하자면 이 문제는 DFS 문제가 아니라, 구현 문제에 가깝다. 하지만 DFS 알고리즘의 핵심이 되는 재귀 함수 구현을 요구한다는 점에서 DFS 연습 목적의 문제로 여기서 다뤄보자!
이 문제를 실수 없이 풀려면 소스코드를 최대한 단순화하는 것이 좋다.
➡️ 따라서 특정 문자열에서 "균형잡힌 괄호 문자열"의 인덱스를 변환하는 함수와 특정한 "균형잡힌 괄호 문자열"이 "올바른 괄호 문자열"인지 판단하는 함수를 별도로 구현한다.
이후에 재귀 함수에서 이 두 함수를 불러온다.
# "균형잡힌 괄호 문자열"의 인덱스 반환
def balanced_index(p):
count = 0 # 왼쪽 괄호의 개수
for i in range(len(p)):
if p[i] == '(':
count += 1
else:
count -= 1
if count == 0:
return i
# "올바른 괄호 문자열"인지 판단
def check_proper(p):
count = 0 # 왼쪽 괄호의 개수
for i in p:
if i == '(':
count += 1
else:
if count == 0: # 쌍이 맞지 않는 경우에 False 반환
return False
count -= 1
return True # 쌍이 맞는 경우에 True 반환
def solution(p):
answer = ''
if p == '':
return answer
index = balanced_index(p)
u = p[:index + 1]
v = p[index + 1:]
# "올바른 괄호 문자열"이면, v에 대해 함수를 수행한 결과를 붙여 반환
if check_proper(u):
answer = u + solution(v)
# "올바른 괄호 문자열"이 아니라면 아래의 과정을 수행
else:
answer = '('
answer += solution(v)
answer += ')'
u = list(u[1:-1]) # 첫 번째와 마지막 문자를 제거
for i in range(len(u)):
if u[i] == '(':
u[i] = ')'
else:
u[i] = '('
answer += "".join(u)
return answerQ18. 괄호 변환
난이도: ⭐⭐
풀이시간: 30분
시간제한: 2초
메모리제한: 512MB
기출: 삼성전자 SW 역량테스트
링크: https://www.acmicpc.net/problem/14888
