백준 algorithm dfs 14888 2573 2617 study python

파이썬 알고리즘 : 연산자 끼워넣기, 빙산, 구슬 찾기

백준 14888, 백준 2573, 백준 2617

2023년 8월 10일 알고리즘 문제풀이

문제 1 백준 14888

문제 링크

1차 시도

나의 생각

각 경우에 알맞은 연산을 처리한 후 재귀를 탔다. 정의한 dfs 재귀 함수는 몇번의 재귀를 탔는지, 각 연산이 몇번 남아있는지를 parameter로 받도록 정의하였다. 나눗셈은 음수일때는 양수로 변환한 후 결과에 음수를 다시 붙이도록 하였다.

결과

정답

코드

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

import sys

n = int(sys.stdin.readline())
nums = list(map(int, sys.stdin.readline().split()))
plus, minus, multiple, division = map(int, sys.stdin.readline().split())

arr = []

def dfs(tmp, cnt, a, b, c, d):
    if cnt == n:
        arr.append(tmp)
        return

    if a:
        tmp += nums[cnt]
        a -= 1
        cnt += 1
        dfs(tmp, cnt, a, b, c, d)
        cnt -= 1
        a += 1
        tmp -= nums[cnt]

    if b:
        tmp -= nums[cnt]
        b -= 1
        cnt += 1
        dfs(tmp, cnt, a, b, c, d)
        cnt -= 1
        b += 1
        tmp += nums[cnt]

    if c:
        tmp *= nums[cnt]
        c -= 1
        cnt += 1
        dfs(tmp, cnt, a, b, c, d)
        cnt -= 1
        c += 1
        tmp = tmp // nums[cnt]

    if d:
        if tmp >= 0:
            tmp = tmp//nums[cnt]
        else:
            r_tmp = abs(tmp)//nums[cnt]
            tmp = -1 * r_tmp
        d -= 1
        cnt += 1
        dfs(tmp, cnt, a, b, c, d)
        cnt -= 1
        d += 1
        if tmp >= 0:
            tmp = abs(tmp)*nums[cnt]
        else:
            r_tmp = abs(tmp)*nums[cnt]
            tmp = -1 * r_tmp


dfs(nums[0], 1, plus, minus, multiple, division)
print(max(arr))
print(min(arr))

문제 2 백준 2573

문제 링크

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
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68

import sys
sys.setrecursionlimit(10**6)

n,m = map(int,sys.stdin.readline().split())
graph = []
for _ in range(n):
    arr = list(map(int,sys.stdin.readline().split()))
    graph.append(arr)

da = [0,-1,0,1]
db = [1,0,-1,0]
melt = [[0 for _ in range(m)] for _ in range(n)]

def dfs(a,b):
    tmp = 0
    for i in range(4):
        new_a = a + da[i]
        new_b = b + db[i]
        if graph[new_a][new_b]:
            tmp += 1
    melt[a][b] = tmp

flag = False
def check(ice):
    global flag
    visited = [[False for _ in range(m)] for _ in range(n)]
    a,b = ice.pop()
    while ice:
        for i in range(4):
            new_a = a + da[i]
            new_b = b + db[i]
            if graph[new_a][new_b]:
                visited[a][b] = True
                ice.append([new_a,new_b])
                check(ice)

    for a in range(1,n-1):
        for b in range(1,m-1):
            if not visited[a][b] and graph[a][b]:
                flag = True
                return

cnt = 0
while True:
    cnt += 1
    ice = []
    for a in range(1,n-1):
        for b in range(1,m-1):
            if graph[a][b]:
                dfs(a,b)

    for a in range(1,n-1):
        for b in range(1,m-1):
            graph[a][b] -= melt[a][b]
            if graph[a][b] < 0:
                graph[a][b] == 0
            elif graph[a][b]:
                ice.append([a,b])

    if not ice:
        cnt = 0
        break
    else:
        check(ice)
        if flag:
            break

print(cnt)

2차 시도

나의 생각

기존에는 주변의 물을 탐색하여 녹을 양을 반환하는 함수, 모든 얼음의 좌표를 나타내는 배열을 통해 얼음을 녹이고 전체 덩어리가 한개 이상인지 확인하는 함수 2개를 정의하였다. 이 둘을 하나로 합쳤다.

정의된 함수 check의 내용은 다음과 같다.

방문 처리를 위한 배열을 만든 후 parameter로 받은 좌표를 방문처리 한다. 이 좌표를 arr 배열에 추가한 후 배열에서 하나씩 pop하며 다음 과정을 거친다. pop한 좌표를 (a,b)라 하였을 때, 좌표의 상하좌우를 모두 탐색하여 아직 방문한적 없는 빙산이 존재하고 있다다면 그 좌표를 배열 arr에 추가한 후 방문처리 하고 cnt를 1 추가한다. 이 과정이 arr배열이 빌 때 까지 반복되고 종료되면 cnt를 반환한다.

이 과정을 통해 한 빙산에서 연결되어 있는, 즉 한 덩어리에 있는 빙산은 모두 방문처리 된다. 이 함수가 종료된 후 방문처리되지 않은 빙산이 있다면, 같은 덩어리에 있지 않다는 의미이므로 빙산이 분리되었다는 것을 의미한다.

입력받은 배열을 정리한 후 빙산이 존재하는 좌표를 배열 ice에 담는다. 함수 check는 cnt를 반환하는데 이는 연결된 얼음의 수 이다. 따라서 ice배열의 길이와 check가 반환한 cnt가 다르다는 의미는 연결되지 않은 빙산이 있음을 의미한다. 이때는 반복문을 종료하고 현재까지 루프가 반복된 횟수 years가 정답이 된다.

아직 한 덩어리일때는 존재하는 얼음들의 배열인 ice를 탐색하게 된다. 각 얼음마다 상하좌우의 물을 파악한 후 1년 뒤 녹는 양을 melt에 저장한다. 그리고 녹는 양이 파악된 빙산의 좌표와 ice배열에서 가지는 index 까지 포함하여 melt_co에 저장한다.

melt 배열은 어떤 좌표의 얼음이 녹을 양을 그 좌표에 표시한 2차원 배열을 의미한다.

반면 melt_co는 ice의 i번째 index인 얼음의 좌표를 표시한다. 이미 물인 좌표들은 탐색할 필요가 없기 때문에 현재 ice라는 배열을 통해 빙산이 존재하는 곳만 연산에 포함하고 있는 상황이다.

이 상황에서 만약 `melt_co` 배열이 없으면 매해 모든 얼음을, 2차원 배열 전체를 탐색하면서 녹아야 할 좌표를 찾고나서 계산해야 하므로 resource 낭비가 심하여 오답처리된다.

melt_co배열의 원소를 통해 ice 배열의 요소들을 알맞게 감소시키고 0보다 이하라면 0으로 고정시키고 더이상 얼음이 아니므로 ice배열에서 제거한다.

i라는 index를 뒤에서부터 순회해야 하는 이유가 있다. 앞에서부터 검사하면 다 녹은 얼음을 pop 한 결과 뒤의 ice 배열들의 index가 바뀐다. 따라서 melt-co에 저장해놓은 index와 실제 index가 달라져서 업데이트가 제대로 안된다. 뒤에서부터 검사하면 pop하더라도 index 변화가 없는 앞의 원소들을 체크해 나가기 때문에 문제가 발생하지 않는다.

코드 작성대로의 흐름으로 설명한 것인데, 조금 더 간결하게 설명해 보겠다.

  1. 현재 얼음이 존재하는 좌표들을 ice배열에 포함시킨다.
  2. 각 얼음 좌표의 상하좌우를 탐색하여 1년 후 녹을 양을 melt에 표시한다.
  3. ice배열의 각 원소의 index와 그 원소가 나타내는 좌표를 melt_co에 저장한다.
  4. melt_co를 순회하며 얼음이 녹은 것을 적용하여 얼음의 양과 ice배열을 업데이트한다.
  5. check함수를 통해 연결되어 있는 빙산의 갯수만 파악한다.
  6. 전체 빙산 갯수와 비교하여 모든 빙산이 연결되어있는지 확인한다.
  7. 모든곳이 연결되어있지 않다면 종료하고, 연결되어 있다면 반복한다.

결과

정답

코드

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

import sys

def check(a, b):
    global n, m
    cnt = 1
    visited = [[False] * m for _ in range(n)]
    visited[a][b] = True

    arr = [(a, b)]
    while arr:
        a, b = arr.pop()

        for dir in range(4):
            na = a + da[dir]
            nb = b + db[dir]

            if not visited[na][nb] and graph[na][nb] != 0:
                arr.append((na,nb))
                visited[na][nb] = True
                cnt += 1

    return cnt

n, m = map(int,sys.stdin.readline().split())
graph = [list(map(int,sys.stdin.readline().split())) for _ in range(n)]
melt = [[0] * m for _ in range(n)]

da = [-1, 0 , 1, 0]
db = [0, 1, 0, -1]

ice = []
for i in range(1, n-1):
    for j in range(1, m-1):
        if graph[i][j] != 0:
            ice.append((i, j))

ans = 0
years = 0
while ice:
    if len(ice) != check(ice[0][0], ice[0][1]):
        ans = years
        break
    years += 1
    melt_co = []
    for i in range(len(ice) - 1, -1, -1):
        a, b = ice[i]

        for dir in range(4):
            na = a + da[dir]
            nb = b + db[dir]

            if graph[na][nb] == 0:
                melt[a][b] += 1

        if melt[a][b] > 0:
            melt_co.append((a, b, i))

    for a, b, i in melt_co:
        graph[a][b] -= melt[a][b]
        if graph[a][b] <= 0:
            graph[a][b] = 0
            ice.pop(i)

        melt[a][b] = 0

print(ans)

문제 3 백준 2617

문제 링크

1차 시도

나의 생각

두가지 2차원 배열을 만들었다. 각 배열은 자신보다 무겁거나, 가벼운 구슬의 번호를 원소로 가진다. 구슬의 모든 번호를 순회하며 배열을 통해 자신보다 무겁거나 가벼운 구슬의 갯수를 확인한다. 또한 재귀를 통해 그 구슬의 무겁거나 가벼운 구슬의 갯수도 포함한다. 이를 통해 관계가 확인된 구슬의 갯수가 전체 구슬의 갯수의 절반보다 1이 큰 숫자, 즉 가운데를 나타내는 숫자보다 크면 가운데에 올수 없음이 확인되므로 정답에 포함시켰다. 혹시 구슬이 중복되어 카운트될까 하여 check를 통해 관계가 확인된 구슬을 표시하도록 하였고 매번 초기화시켰다.

주어진 예시는 결과값이 알맞게 나오는데, 오답처리가 되는걸로 보아 예외 case가 있는것 같다..

결과

오답

코드

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

import sys
sys.setrecursionlimit(10**6)

n,m = map(int,sys.stdin.readline().split())
arr_h = [[] for _ in range(n+1)]
arr_l = [[] for _ in range(n+1)]
for _ in range(m):
    heavy,light = map(int,sys.stdin.readline().split())
    arr_h[heavy].append(light)
    arr_l[light].append(heavy)

def dfs(i):
    global cnt
    check = [0 for _ in range(n+1)]
    for x in arr_h[i]:
        check[x] = 1
        for j in arr_h[x]:
            if not check[j]:
                check[j] = 1
    if num <= sum(check):
        cnt += 1
        return

    check = [0 for _ in range(n+1)]
    for x in arr_l[i]:
        check[x] = 1
        for j in arr_l[x]:
            if not check[j]:
                check[j] = 1
    if num <= sum(check):
        cnt += 1
cnt = 0
num = n//2 + 1
for i in range(1,n+1):
    dfs(i)
print(cnt)

2차 시도

나의 생각

원인을 찾아냈다! 기존 방법에서는 한 구슬을 조사할 때 그 구슬과 바로 1차적으로 관계가 있는 구슬만 추가로 조사하였다. 하지만 재귀를 통해 관계가 있는 모든 구슬을 파악했어야 했다.

예를 들어 2번 구슬보다 무거운 구슬이 4번,7번 구슬이라고 하면 기존에는 4번과 7번 각각의 구슬보다 무거운 것이 있는지 파악하였다. 예를 들어 4번 구슬은 12,14번 구슬보다 무겁고 7번 구슬은 8번 구슬보다 무겁다면, 2번 구슬의 경우 결국 4,7,12,14,8 5개까지만 파악하게 된다. 그런데 만약 14번 구슬보다 무거운 것이 24,26,31,35 번 구슬이 있다면? 기존 코드에는 여기 깊이까지는 도달하지 않았다. 단순 loop를 통해서만 구현했기 때문이다.

따라서 재귀를 통해 끝까지 모든 구슬의 관계를 파악하였더니 정답처리 되었다.

결과

정답

코드

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
sys.setrecursionlimit(10**6)

n,m =map(int,sys.stdin.readline().split())
arr_h=[[] for _ in range(n+1)]
arr_l=[[] for _ in range(n+1)]

for i in range(m):
    heavy,light=map(int,input().split())
    arr_h[heavy].append(light)
    arr_l[light].append(heavy)

def dfs(arr, n):
    global cnt
    for i in arr[n]:
        if not visited[i]:
            visited[i]=True
            cnt += 1
            dfs(arr,i)

num= n//2 + 1
ans=0

for i in range(1,n+1):
    visited = [False for _ in range(n+1)]
    cnt = 0
    dfs(arr_h,i)
    if cnt >= num:
        ans += 1
    cnt = 0
    dfs(arr_l,i)
    if cnt >= num:
        ans += 1

print(ans)
CATALOG
    algorithm