2023년 8월 25일 알고리즘 문제풀이
문제 1 백준 3055
1차 시도
나의 생각
물을 따로 생각하지 말고 이미 방문해서 방문할 수 없는 곳으로 처리한다면 크게 복잡하지 않을 수도 있겠다는 생각을 했다. 따라서 고슴도치가 이동할 곳을 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
import sys
from collections import deque
r,c = map(int,sys.stdin.readline().split())
forest = []
for _ in range(r):
forest.append(list(sys.stdin.readline().rstrip()))
animal = deque()
water = deque()
visited = [[0 for _ in range(c)] for _ in range(r)]
for i in range(r):
for j in range(c):
if forest[i][j] == 'D':
arrive_a = i
arrive_b = j
if forest[i][j] == 'S':
animal.append([i,j,0])
if forest[i][j] == '*':
visited[i][j] = -1
water.append([i,j])
if forest[i][j] == 'X':
visited[i][j] == -2
da = [1,0,-1,0]
db = [0,1,0,-1]
now = 0
ans = 'KAKTUS'
while animal:
a,b,t = animal.popleft()
if visited[a][b] == -1:
continue
if a == arrive_a and b == arrive_b:
ans = now
break
if now != t:
now = t
for i in range(4):
if water:
water_a, water_b = water.popleft()
new_water_a = water_a + da[i]
new_water_b = water_b + db[i]
if new_water_a < 0 or new_water_a >= r or new_water_b < 0 or new_water_b >= c:
continue
visited[new_water_a][new_water_b] = -1
water.append([new_water_a,new_water_b])
for i in range(4):
na = a + da[i]
nb = b + db[i]
if na < 0 or na >= r or nb < 0 or nb >= c:
continue
if visited[na][nb] == 0:
animal.append([na,nb,t+1])
print(ans)
2차 시도
나의 생각
분마다 고슴도치의 이동과 물의 이동을 조절해야 했다. 기존대로 while문을 통해서는 힘들어서 함수를 정의했다. 함수가 정의되었을 떄 큐의 길이를 저장하고 저장된 큐의 길이만큼만 반복문을 반복하도록하여 물의 이동이 1분만 적용될 수 있도록 하였다. 로직은 다음과 같다. bfs도 마찬가지로 분 단위로 조절되야 하므로 고슴도치의 이동 가능한 곳을 저장하는 배열의 길이를 저장하였다. 그리고 매 분 그 길이만큼만 반복문이 수행되도록 하였다.
이전과 마찬가지로 visited배열에 방문 처리와 동시에 시간을 표시하도록 하였다. 우선 입력이 끝나면 모든 좌표를 순회하여 고슴도치가 위치한 곳을 찾아 저장하고, 그 위치를 비어있는 곳(‘.’)으로 바꿔 표시하였다. 나중에 물이 들어올 수 있도록 하기 위함이다. 또한 처음 물의 위치도 찾아 물을 위하 배열 water에 저장하였다.
물의 이동을 업데이트하는 함수 flood는 호출되면 가장 먼저 현재 물이 있는 좌표들의 배열인 water의 길이를 저장한다. 그리고 그 길이만큼 반복문을 반복하며 주변에 물이 이동할 수 있는 곳을 찾아 이동시키고 water배열에 추가한다. 길이만큼 해야하는 이유는, 1분 동안 발생하는 물의 이동만 업데이트해야 되기 때문이다. water배열은 물이 이동하면서 계속 추가되기 때문에 길이를 통해 반복문의 횟수를 제어하지 않으면 모든 칸에 물이 차버릴 것이다.
bfs 함수도 마찬가지이다. parameter로 고슴도치의 위치를 받고 고슴도치가 이동할 수 있는 곳의 좌표들을 배열 arr에 저장한다. 기존처럼 배열이 존재하는 한 반복되도록 하되, 1분 단위로 끊어야 하므로 arr의 길이를 저장하여 그만큼만 반복문을 통해 다음 이동할 수 있는 좌표를 저장한다. 이 과정에서 고슴도치가 비버의 굴에 도착한다면 함수를 종료하면 된다. 고슴도치의 이동 좌표 탐색이 끝나면 flood함수를 호출하여 1분 동안 물의 이동을 업데이트한다. 이 후 새로운 배열 arr의 상태로 반복한다.
마지막에 bfs함수 전에 먼저 flood함수를 호출하는 이유는 문제에서 “고슴도치는 물이 찰 예정인 칸으로 이동할 수 없다” 라는 조건 떄문이다. 우선 물을 이동 시키고 고슴도치를 이동시키면 이 조건으로 인한 문제가 발생할 경우가 사라지기 때문이다.
결과
정답
코드
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
import sys
from collections import deque
r, c = map(int, sys.stdin.readline().split())
forest = []
for _ in range(r):
forest.append(list(sys.stdin.readline().rstrip()))
visited = [[0 for _ in range(c)] for _ in range(r)]
arr = deque()
water = deque()
for i in range(r):
for j in range(c):
if forest[i][j] == 'S':
animal_a, animal_b = i, j
forest[i][j] = '.'
elif forest[i][j] == '*':
water.append([i, j])
da = [1, 0, -1, 0]
db = [0, 1, 0, -1]
def flood():
num = len(water)
while num:
a, b = water.popleft()
for i in range(4):
na = a + da[i]
nb = b + db[i]
if na < 0 or na >= r or nb < 0 or nb >= c:
continue
if forest[na][nb] == '.':
forest[na][nb] = '*'
water.append([na, nb])
num -= 1
def bfs(p, q):
arr.append([p, q])
visited[p][q] = 1
while arr:
num = len(arr)
while num:
a, b = arr.popleft()
for i in range(4):
na = a + da[i]
nb = b + db[i]
if na < 0 or na >= r or nb < 0 or nb >= c:
continue
if visited[na][nb] == 0 and forest[na][nb] == '.':
visited[na][nb] = visited[a][b] + 1
arr.append([na, nb])
elif forest[na][nb] == 'D':
print(visited[a][b])
return
num -= 1
flood()
print('KAKTUS')
return
flood()
bfs(animal_a, animal_b)
문제 2 백준 2294
1차 시도
나의 생각
모든 경우의 수를 탐색하며 결과가 나오면 출력하고 아니면 -1을 출력하도록 생각했다 .탐색은 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
import sys
from collections import deque
n, k = map(int, sys.stdin.readline().split())
coin = [0]
for _ in range(n):
coin.append(int(sys.stdin.readline()))
coin.sort(reverse=True)
def bfs(x):
arr = deque()
ans = 0
arr.append(x)
while arr:
ans += 1
cnt = len(arr)
while cnt:
tmp = arr.popleft()
for x in coin:
if x+tmp == k:
return ans
elif x+tmp < k:
arr.append(x+tmp)
cnt -= 1
return -1
ans = bfs(0)
print(ans)
2차 시도
나의 생각
우선 가치가 똑같은 동전은 굳이 배열에서 여러개 둘 필요가 없다는 생각이 들었다. 따라서 set을 통해 중복을 줄였다. 그리고 같은 가격을 만들어 내도 방법이 다르면 저장되고 있었다. 1000원을 만든다면 과정에서 100원을 10번 써서 만들어져도, 500원 2번 써서 만들어져도 내 배열에는 모두 저장된다. 이미 500원 2번 써서 만들었다면 100원을 10번 썼을 때 저장할 필요가 없었다. 이 저장된 배열이 순회하며 계산되므로 불필요한 저장을 줄여야 했다. 따라서 결과를 리스트에 넣지 않고 값을 index로 하는 visited를 만들었다. 목표인 k원 이상은 생각할 필요가 없으므로 index는 0부터 k까지였다. 동전으로 어떤 값이 만들어진 순간 그 값을 index로 하는 visited가 0이라면 현재까지 쓰인 동전의 갯수를 저장한후에 큐에 집어넣는다.. 이후에는 그 값이 만들어져도 이미 최소의 동전으로 만드는 방법이 저장되어 있으므로 큐에 저장할 필요가 없다.
결과
정답
코드
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
import sys
from collections import deque
n, k = map(int, sys.stdin.readline().split())
coin = set()
for _ in range(n):
tmp = int(sys.stdin.readline())
coin.add(tmp)
coin = list(coin)
visited = [0 for _ in range(k+1)]
def bfs():
arr = deque()
for i in coin:
if i == k:
return 1
if i < k:
visited[i] = 1
arr.append(i)
while arr:
money = arr.popleft()
for i in coin:
if money+i > k:
continue
elif money+i == k:
return visited[money]+1
elif money+i <= k and not visited[money+i]:
arr.append(money+i)
visited[money+i] = visited[money]+1
return -1
ans = bfs()
print(ans)
문제 3 프로그래머스 영어 끝말잇기
1차 시도
나의 생각
반복문을 통해 현재 몇번째 사람이 말할 차례인지, 몇바퀴를 돌았는지를 나타내는 값을 증가시켰다.
결과
정답
코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def solution(n, words):
flag = False
ans_1 = 1
ans_2 = 0
for i in range(1,len(words)):
if flag:
break
ans_1 += 1
if ans_1 > n:
ans_1 -= n
ans_2 = i//n + 1
if words[i-1][-1] != words[i][0]:
flag = True
break
for j in range(i):
if words[j] == words[i]:
flag = True
break
if not flag:
ans_1 = ans_2 = 0
answer = [ans_1,ans_2]
return answer
