코딩 테스트 준비 - 탐색(2)
지난 글에 이어 이번글에서 제가 푼 탐색 문제들을 리뷰하면서 얻을 수 있는 팁들을 정리해보겠습니다.😀
10451 - 순열 사이클, 2331 - 반복 수열
문제 해석
이 두 문제에서는 순열/수열의 수를 노드로 보고 그 때 마다 연결된 노드를 계산해서 구한다고 생각하면 단방향 그래프로도 볼 수 있죠!
그러면 주어진 첫 수를 루트 노드로 하여 cycle이 생길 때 까지 탐색을 진행하면 됩니다.
순열 사이클은 이전의 연결 요소 구하기 문제 처럼 주어진 순열을 순회하며 cycle의 개수를 구하면 되고
반복 수열은 이렇게 탐색을 해서 얻은 루트 노드를 얻고 수열에서 이 노드가 나오는 순서를 구하면 됩니다.
길이 한 갈래 밖에 없다는 점에서 굳이 그래프 개념을 도입해서 탐색을 하기 보다 그냥 단순히 주어진 문제를 잘 보고 구현하면 되긴합니다.😅
이전 문제와의 차이점
이전 글에서 풀었던 문제와 다른 점으로는 그래프의 정보를 직접적으로 주지 않는다는 것입니다. 이전 문제들에선 연결된 두 노드의 정보들을 입력에서 모두 주었지만, 이 문제들은 노드들간 연결관계를 생각하여 알아내야 하기 때문에 탐색을 구현하는 연습을 하기에 좋은 문제들이라고 느껴집니다.
- 문제에서 다음 노드의 힌트를 얻자
1697 - 숨바꼭질, 5014 - 스타트 링크
문제 해석
이 둘은 무난한 최단거리 문제로 볼 수 있겠습니다.
최단거리 문제는 DFS가 아닌 BFS로 풀어야 한다는 점을 알아야 하고, 이 두 문제 역시 문제를 보고 다음 방문할 노드를 구할 수 있어야 하는데요
앞의 두 문제와는 달리 다음 방문할 노드가 1개가 아니라 여러개이기 때문에 모든 노드를 방문할 수 있는 탐색기법을 적용해야 하고 그중에서도 최단거리를 구할 수 있는 BFS를 사용해야 합니다!
둘 다 정답률이 생각보다 낮은 이유는 함정이 하나씩 숨어 있기 때문인 것 같습니다. (저도 이 함정들에 한번 씩 걸렸습니다😂)
함정?
숨바꼭질 문제는 주어진 좌표 범위가 0부터 시작하기 때문에 0에서 X-1로 갈 경우 좌표가 음수가 될 수 있음을 유의해야 합니다.
동생은 항상 양수 좌표에 존재하기 때문에 좌표가 음수가 될 경우는 최단 거리가 될 수 없기 때문에 이동한 좌표가 음수인 경우는 배제 하는 것이 좋습니다.(방문을 배열로 구현할 경우 인덱스 에러남😕)
스타트 링크는 최대 층수가 F로 정해져 있기 그보다 높은 층수는 방문할 수 없도록 잘 구현해야 합니다.(사실 이건 함정이라기 보단 당연한건데 제가 깜빡한듯..)
- 문제를 보고 다음 방문할 노드의 조건을 찾자
- 범위에 대해서 항상 체크하기
이번 문제부터는 좀 더 꼼꼼하게 보도록 하겠습니다.
2468 - 안전영역
개인적으로 구현하는데 많은 시간이 걸린 문제입니다..!
문제 해석
안전한 영역의 최대 개수를 구하는 것이 목표인데요
안전한 영역의 최대 개수를 구하려면 각 비의 양에 따라서 안전한 영역의 개수를 구해야 하고 안전한 영역이란 비에 잠기지 않는 상하좌우로 연결된 영역이므로
비에 잠기지 않는 칸을 먼저 구하고 이에 인접한 칸이 비의 높이보다 큰 지를 고려하며 탐색을 하면 하나의 안전 영역을 구할 수 있습니다.
2차원 공간이 최대 100x100 크기이고 지역의 최대 높이도 100이기 때문에 모든 영역을 순화하며 위와 같은 조건이라면 루트 노드로 정하고 탐색을 하여 모든 안전 영역의 개수를 구할 수 있습니다.
이렇게 안전 영역의 개수를 구하는 건 이전에 풀었던 연결 요소의 개수 와 순열 사이클 연결 요소의 개수를 구하는 문제와 유사합니다! 다른 점은 방문 조건에 일정 높이 이상이어야 하는 것이 추가 되었다는 것 뿐이죠.
그리고 이를 비가 0~100까지 올 경우에 따라 반복하고 안전 영역의 개수를 비교하여 최댓값을 구하면 됩니다. (100 이상은 100과 같으므로 구할 필요가 없음)
주의할 점
또 주의할 점은 비의 높이가 1 미만으로 내릴 경우를 꼭 포함해야한다는 점입니다. 만약 이를 고려하지 않으면 모든 건물의 높이가 1일 경우를 통과하지 못합니다.
구현 코드
이를 구현한 코드는 아래와 같습니다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
import sys
input = sys.stdin.readline
print = sys.stdout.write
from collections import deque
N = int(input().rstrip())
h_map = [[0 for _ in range(N+1)] for _ in range(N+1)]
for i in range(1,N+1):
h_map[i] = list(map(int, input().rstrip().split()))
h_map[i].insert(0,0)
queue = deque()
max = 0
#print("%s\n" %h_map)
# 빗물의 높이 0 ~ 100 반복
for r_height in range(0, 101):
visited = [[False for _ in range(N+1)] for _ in range(N+1)]
cnt = 0
# 빗물의 높이 마다 각 지점의 안전 여부를 확인
for i in range(1, N+1):
for j in range(1, N+1):
# 지점이 침수 지역이거나 이미 탐색한 지역이면 탐색하지 않음
#print("i:%d j:%d\n" %(i,j))
if h_map[i][j] <= r_height or visited[i][j]:
continue
# 아닐 시에 카운트하고 탐색 시작
cnt += 1
visited[i][j] = True
root = (i,j)
queue.append(root)
while queue:
r,c = queue.popleft()
#print("%d %d" %(r,c))
if c+1 <= N and not visited[r][c+1] and h_map[r][c+1] > r_height:
visited[r][c+1] = True
queue.append((r,c+1))
if c-1 >= 1 and not visited[r][c-1] and h_map[r][c-1] > r_height:
visited[r][c-1] = True
queue.append((r,c-1))
if r+1 <= N and not visited[r+1][c] and h_map[r+1][c] > r_height:
visited[r+1][c] = True
queue.append((r+1,c))
if r-1 >= 1 and not visited[r-1][c] and h_map[r-1][c] > r_height:
visited[r-1][c] = True
queue.append((r-1,c))
#print("r_h:%d cnt:%d\n" %(r_height, cnt))
if cnt > max:
max = cnt
print("%d\n" %max)
2차원 공간에서 효율적으로 다음 방문 노드 구하기
탐색 문제는 이런식으로 2차원 공간을 탐색하는 경우가 많은데요. 이런 문제의 경우 저는 위처럼 상,하,좌,우 4개의 조건문을 통해서 다음 방문할 노드를 처리했는데요
다른 사람들의 코드를 참고해보니
1
2
dx = (0,0,1,-1)
dy = (1,-1,0,0)
이런식으로 인덱스에 따라 x,y 값을 미리 정해두고 반복문을 돌며 처리하는 것을 보았습니다. 이를 위 문제에 적용을 시켜보면
1
2
3
4
5
6
7
8
9
10
11
12
if c+1 <= N and not visited[r][c+1] and h_map[r][c+1] > r_height:
visited[r][c+1] = True
queue.append((r,c+1))
if c-1 >= 1 and not visited[r][c-1] and h_map[r][c-1] > r_height:
visited[r][c-1] = True
queue.append((r,c-1))
if r+1 <= N and not visited[r+1][c] and h_map[r+1][c] > r_height:
visited[r+1][c] = True
queue.append((r+1,c))
if r-1 >= 1 and not visited[r-1][c] and h_map[r-1][c] > r_height:
visited[r-1][c] = True
queue.append((r-1,c))
이 부분을
1
2
3
4
5
6
7
for k in range(4):
next_r = r+dy[k]
next_c = c+dx[k]
if (1 <= next_r <= N) and (1 <= next_c <= N):
if not visited[next_r][next_c] and h_map[next_r][next_c] > r_height:
visited[next_r][next_c] = True
queue.append((next_r, next_c))
이렇게 보다 깔끔하게 코드를 작성할 수 있습니다!👏👏
- n차원 공간에서 다음 방문할 노드를 구할 때 각 방향 마다 계산할 좌표 이동값을 저장한 뒤 반복문을 이용해서 효율적으로 코드를 짜자
7576 - 토마토
정말정말 중요하다고 생각하는 문제입니다!
문제 풀이
바이러스 이 문제와 주어진 상황 자체는 유사합니다만 이 문제에서 최초 바이러스가 1번 컴퓨터에 1개로 고정되어 있는 것에 비해
이 토마토 문제에서는 익은 토마토가 입력으로 여러개 주어진다는 것입니다.
처음에 저는 이 문제를 보고 ‘연결요소를 구하는 것 처럼 토마토를 순회하면서 BFS를 여러번 진행해야 하나?’ 생각 했었습니다. 하지만 이런 방법은 동시에 전파되는 상황을 나타낼 수 없었습니다.
‘그럼 다른 토마토가 전파 시켜 익혀진 토마토면 depth를 비교해서 갱신해야하나?’ 이런생각도 해보았지만 python3로는 시간초과가 됐고 pypy3에서는 틀렸다고 나왔습니다. 결국 마땅한 아이디어가 생각나지 않아 답을 보았는데
방법은 생각보다 간단했습니다.
토마토를 순회하면서 익은 토마토를 먼저 queue에 넣으면 되는 것이었는데요 그 후에 BFS를 통해 탐색하면서 도달한 가장 깊은 깊이를 구하면 되는 것이었습니다.
그리고 끝까지 익지 않은 토마토는 익지 않은 토마토인데 방문하지 않은 조건으로 찾아낼 수 있습니다.
구현 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
import sys
from collections import deque
input = sys.stdin.readline
dm = (1,-1,0,0)
dn = (0,0,1,-1)
M,N = map(int, input().rstrip().split())
tomato = [ [0 for _ in range(M)] for _ in range(N)]
# 방문 여부
visited = [ [False for _ in range(M)] for _ in range(N)]
for n in range(N):
tomato[n] = list(map(int, input().rstrip().split()))
queue = deque()
# 익은 토마토 모두 방문하고 queue에 넣기
for n in range(N):
for m in range(M):
if tomato[n][m] == 1:
visited[n][m] = True
queue.append((n,m,0))
max = 0
# 여러 누트노드에서 한 level씩 탐색 시작
# 가장 높은 level을 max에 저장
while queue:
n,m,d = queue.popleft()
if max < d:
max = d
#print(n,m,d)
# 익은 토마토 전파
for i in range(4):
# 가장자리 체크
next_n = n+dn[i]
next_m = m+dm[i]
if ((0 <= next_n < N) and (0<= next_m < M)):
# 안익은 토마토에 전파
if tomato[next_n][next_m] == 0 and not visited[next_n][next_m]:
visited[next_n][next_m] = True
queue.append( (next_n, next_m, d+1) )
for n in range(N):
for m in range(M):
if tomato[n][m] == 0 and not visited[n][m]:
print("-1")
exit()
print(max)
# 시작점이 여러개일 수도 있다..!!, 루트노드가 명확하게 여러개가 주어진다면 동시 탐색을 할 것
‘너비 우선 탐색’ 이라는 속성을 잘 알고 있어야 하는 문제라고 생각합니다.
그동안 풀어온 모든 탐색 문제의 루트 노드는 1개였기 때문에 ‘탐색의 루트 노드는 1개’ 라는 저의 고정관념을 깨게 해준 고마운😌 문제였습니다.
- 여러개의 루트 노드에서 동시에 탐색을 할 수도 있다.
14503 - 로봇 청소기
문제 해석
이 문제도 유형을 따지면 탐색과 구현 그 언저리에 있는 문제인 것 같습니다. 단순하게 보면 문제를 잘 읽고 그대로 구현을 해내면 되는 문제이지만, 그 구현을 하는 내용이 탐색이기 때문입니다.
정석적인 BFS나 DFS와는 탐색하는 알고리즘에 차이가 있는데요, 이번에는 문제의 풀이보다는 어떤 부분이 정석적인 탐색과 다른지를 한번 살펴보겠습니다.
BFS/DFS와 문제 비교
일단 목표는 총 청소한 칸 수의 합을 구하는 것인데요 칸을 방문하는데 청소되지 않은 경우 청소를 하기 때문에
청소 == 방문 표시 라고 볼 수 있을 것 같습니다.
현재 칸의 주변 칸 중 청소되지 않은 빈 칸이 없는 경우, 바라보는 방향을 유지한 채로 한 칸 후진할 수 있다면 한 칸 후진하고 1번으로 돌아간다. 바라보는 방향의 뒤쪽 칸이 벽이라 후진할 수 없다면 작동을 멈춘다. 현재 칸의 주변 칸 중 청소되지 않은 빈 칸이 있는 경우, 반시계 방향으로 90도 회전한다. 바라보는 방향을 기준으로 앞쪽 칸이 청소되지 않은 빈 칸인 경우 한 칸 전진한다.
차이점: DFS나 BFS는 방문할 곳이 없으면 탐색을 멈추지만 여기서는 특정 행동을 수행합니다.
그리고 좌표 개념에 더해 방향 개념이 추가되고 분기가 나뉘지 않는 대신 이 방향에 따라서 다음번에 방문할 칸의 순서를 정합니다.
따라서 BFS나 DFS는 아니지만 특정 조건대로 동작하는 탐색 과정이었습니다. 평소에 하던 2차원 탐색에서 방향 개념이 추가되어 이를 잘 구현하는 것이 핵심이었던 문제입니다!
- 문제를 보고 DFS/BFS인지 특정 탐색 방법을 구현하는지를 구분하자
9205 - 맥주 마시면서 걸어가기
문제 해석
시작점과 끝 점이 하나의 연결 요소에 포함되어 있는지를 확인하면 되는 문제입니다. 여기서 재밌는 점은 그래프 정보를 직접적으로 주는 것이 아니라 해당 노드의 좌표 값을 통해서 직접 구해야 한다는 것입니다!
다른 2차원 공간 문제들도 어떻게 보면 그래프 연결 정보를 그때그때 판단해 만들어 가는 것이지만 이렇게 입력으로 준 노드의 정보를 직접 거리 계산해서 그래프를 만드는 건 처음인 것 같습니다.
이 모든 노드들이 서로 연결되어 있는지를 확인하는 것은 O(n²)이지만 n의 크기가 최대 102였기 때문에 충분한 시간안에 해결할 수 있습니다.
그렇게 그래프 정보를 만들었다면 시점점부터 BFS나 DFS로 탐색을 해서 끝점에 도달할 수 있는지만 확인하면 됩니다.
거리는 항상.. 양수
저는 이문제를 풀 때 어이없는 실수를 해서 해맸는데요 이 문제에서 거리를 구할 때는 맨해튼 거리 방식을 이용해야 합니다.
1
distance = (node2[0] - node1[0]) + (node2[1] - node1[1])
무언가 이상한 점을 눈치채셨나요?
네. 거리인데 절댓값을 안붙였습니다🙄
1
distance = abs(node2[0] - node1[0]) + abs(node2[1] - node1[1])
이렇게 돼야 하죠.. 여러분은 저처럼 어이없는 실수 하지 않으시길🥲
- 거리는 항상 양수이어야 한다!
2573 - 빙산
빙산
대망의 마지막 문제입니다..!(드뎌)
문제 해석
한 덩어리로 주어진 빙산이 두 덩어리 이상으로 분리되는 최초의 시간(년)을 구해야 합니다. 빙산은 각 칸마다 다른 높이를 가지고 있구요.
일단 빙산을 찾아야 한 덩어리인지, 두 덩어리 이상인지를 알 수 있기 때문에 주어진 2차원 배열을 순회하면서 루트 노드를 찾아야겠습니다. 빙산은 양수 바다는 0이기 때문에 0인지를 판단해서 루트 노드를 찾을 수 있겠습니다.
그 후에는 BFS/DFS를 이용한 탐색을 진행합니다.
다시 순회하면서 방문하지 않은 빙하가 있다면 두 덩어리 이상인 것이므로 더 볼 것 없이 해당 년도가 정답입니다!
만약 빙하가 여전히 한 덩어리라면 빙하를 녹여야 하는데 녹이려면 각 빙하에 대해서 주변 바다와 인접한 면의 개수를 알아야합니다. 따라서 탐색을 진행하면서 이를 계산해야 합니다.
주의할 점
여기서 중요한 점은 계산한 결과를 저장만하고 빙산을 바로 녹이면 안됩니다! 빙산은 1년마다 녹기 때문에 이를 바로 반영시키면 각 칸의 빙하마다 시간축이 달라지는 것이죠!!
아 그리고 모든 빙하가 녹았는데도 두 덩어리로 나뉘지 않은 케이스도 고려해야 하기 때문에 빙산을 녹일 때 모든 빙산이 녹았는지도 체크를 해주어야 합니다.
여기까지 했으면 논리적으로 오류가 없는 것 같아 제출했는데 시간 초과가 됐습니다.😡
최적화
그래서 최적화 하는 방법을 생각해 보았습니다.
최대 300*300의 배열이 주어지기 때문에 이를 순회하면서 빙산을 찾는 과정에서 1년 당 약 100,000의 연산을 하게 됩니다. 하지만 문제에서 빙산이 차지하는 칸의 개수는 10,000개 이하임을 알려주었습니다. 따라서 처음에 빙산이 있는 지점만을 순회한다면 순회하는 횟수가 최대 10,000회를 넘지 않습니다.
따라서 저는 배열을 사용하는 대신 딕셔너리를 사용하여 처음 주어진 배열을 순회하며 빙산이 존재하는 칸을 저장하고 순회를 할 때 이를 이용했습니다.
다행히 이렇게 수정하니 제한 시간안에 통과할 수 있었습니다!! 😙
구현 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
import sys
from collections import deque
input = sys.stdin.readline
N, M = map(int, input().rstrip().split())
ice = [list(map(int, input().rstrip().split())) for _ in range(N)]
ice_dict = {}
for i in range(N):
for j in range(M):
if ice[i][j] > 0:
ice_dict[(i,j)] = ice[i][j]
def count_around_sea(i,j):
cnt = 0
if ice[i-1][j] == 0:
cnt += 1
if ice[i][j+1] == 0:
cnt += 1
if ice[i][j-1] == 0:
cnt += 1
if ice[i+1][j] == 0:
cnt += 1
return cnt
def search_next_ice(i,j):
if ice[i-1][j] > 0 and not visited[i-1][j]:
return (i-1,j)
if ice[i][j+1] > 0 and not visited[i][j+1]:
return (i,j+1)
if ice[i][j-1] > 0 and not visited[i][j-1]:
return (i,j-1)
if ice[i+1][j] > 0 and not visited[i+1][j]:
return (i+1,j)
return False
# 빙산이 다 녹을 때 까지 BFS를 반복
cnt = 0
all_melt = False
while not all_melt:
melt_count = {}
first_find = True
visited = [ [False for _ in range(M)] for _ in range(N)]
queue = deque()
# 빙산을 탐색하기
for key in ice_dict:
i,j = key
if ice[i][j] > 0 and first_find:
first_find = False
visited[i][j] = True
queue.append((i,j))
while queue:
r,c = queue.popleft()
melt_count[(r,c)] = count_around_sea(r,c)
if ice[r][c+1] > 0 and not visited[r][c+1]:
visited[r][c+1] = True
queue.append((r,c+1))
if ice[r][c-1] > 0 and not visited[r][c-1]:
visited[r][c-1] = True
queue.append((r,c-1))
if ice[r+1][c] > 0 and not visited[r+1][c]:
visited[r+1][c] = True
queue.append((r+1,c))
if ice[r-1][c] > 0 and not visited[r-1][c]:
visited[r-1][c] = True
queue.append((r-1,c))
# 이후에 방문하지 않은 다른 빙산을 찾으면 2개 이상으로 갈라진 것
elif ice[i][j] > 0 and not visited[i][j] and not first_find:
print(cnt)
exit()
all_melt = True
cnt += 1
for key in melt_count.keys():
r,c = key
if ice[r][c] - melt_count.get(key) < 0:
ice[r][c] = 0
else:
all_melt = False
ice[r][c] -= melt_count.get(key)
print("0")
# 2차원 배열이 탐색 시간이 오래 걸린다면 딕셔너리를 활용하자
막 에쁘게 짠 코드가 아닌지라 개선을 시켜야 할것 같습니다..!
- 탐색하는 그래프의 정보를 변경해야 하는 작업이 있다면 변경 시점을 잘 고려하자
- 방문 체크를 하는 visited 배열이 너무 크다면 딕셔너리를 이용하자. 시간복잡도O(1)을 유지하면서 효율적으로 메모리를 사용할 수 있다.
마치며
이렇게 길고도 긴 탐색 문제 리뷰가 끝났습니다..! 저는 DFS/BFS가 모두 가능한 문제일 때 BFS만을 이용해서 풀었기 때문에 DFS풀이도 좀 더 연습해 봐야겠습니다. 그럼 여기까지 읽어주신 분들 모두 조금이나마 팁을 얻어가시면 좋겠습니다!
감사합니다☺️