[이.취.코] Chap 5. DFS - 음료수 얼려 먹기

@mildsalmon·2021-08-16 16:38

1. 음료수 얼려 먹기

난이도
- 중하
풀이 시간
- 30분
시간 제한
- 1초
메모리 제한
- 128MB

A. 문제

N*M 크기의 얼음 틀이 있다.

구멍이 뚤려 있는 부분은 0, 칸막이가 1로 표시된다.

상, 하, 좌, 우로 붙어 있는 경우 서로 연결되어 있는 것으로 간주한다.

이때 생성되는 총 아이스크림의 개수를 구하는 프로그램을 작성하라.

a. 예를 들면.

4 * 5 얼음 틀.

일때 아이스크림은 총 3개 생성된다.

b. 입력 조건

첫 번째 줄에 얼음 틀의 세로 길이 N과 가로 길이 M이 주어진다
- (1 <= N, M <= 1000)
두 번째 줄부터 N+1번째 줄까지 얼음 틀의 형태가 주어진다.
- 구멍이 뚫려있는 부분은 0
- 그렇지 않은 부분은 1

c. 출력 조건

한 번에 만들 수 있는 아이스크림의 개수를 출력하라.

d. 테스트 케이스

입력 예시


15 14
00000111100000  
11111101111110  
11011101101110  
11011101100000  
11011111111111  
11011111111100  
11000000011111  
01111111111111  
00000000011111  
01111111111000  
00011111111000  
00000001111000  
11111111110011  
11100011111111  
11100011111111

출력 예시
```
8
```

B. 내 답안

a. 첫 트라이 - 실패


# n, m = map(int, input().split())  
ice = []  
  
checks = []  
ice_count = 0  
total_zero_count = 0  
move_check = ((0, -1), (1, 0), (0, 1), (-1, 0))  
start_point_y = 0  
start_point_x = 0  
start_point = -1  
move_check_count = 0  
  
n, m = 15, 14  
z =['00000111100000',  
 '11111101111110',  
 '11011101101110',  
 '11011101100000',  
 '11011111111111',  
 '11011111111100',  
 '11000000011111',  
 '01111111111111',  
 '00000000011111',  
 '01111111111000',  
 '00011111111000',  
 '00000001111000',  
 '11111111110011',  
 '11100011111111',  
 '11100011111111']  
  
  
for i in range(n):  
    a = list(map(int, z[i]))  
  
    ice.append(a[:])  
    # check.append(a[:])  
  
 for j in range(m):  
        # print('a[j]', a[j])  
 if a[j] == 0:  
            total_zero_count = total_zero_count + 1  
  
 if start_point == -1:  
        try:  
            start_point_y = a.index(0)  
            print("start_point, start_point_y_1", start_point, start_point_y)  
            start_point = 0  
        except Exception as e:  
            start_point == -1  
            start_point_y = 0  
        start_point_x = i  
# print("zero_count", total_zero_count)  
for k in range(n):  
    start_point = -1  
    checks.append([start_point_x, start_point_y])  
    print("checks_1", checks)  
  
    while checks:  # check in checks:  
        dx = checks[-1][0]  
        dy = checks[-1][1]  
        ice[dx][dy] = 1  
        print("checks_3", checks)  
        move_check_count = 0  
        print(*ice, sep='\n')  
        for l in move_check:  
            print("l", l)  
            nx = dx + l[0]  
            ny = dy + l[1]  
            # print("nx,ny", nx,ny)  
            # print("ice_2", ice[nx][ny]) 
            if nx >= 0 and nx < n and ny >= 0 and ny < m:  
                print("nx,ny", nx, ny)  
                print("ice", ice[nx][ny])  
                if ice[nx][ny] == 0:  
                    checks.append([nx, ny])  
                    print("checks_2", checks)  
  
                    print(*ice, sep='\n')  
                    break  
                else:  
                    pass  
  
            move_check_count = move_check_count + 1  
            print("move_check_count", move_check_count)  
        if move_check_count == 4:  
            print("move_check_count", "4")  
            checks.pop()  
  
    if start_point == -1:  
        try:  
            start_point_y = ice[k].index(0)  
        except Exception as e:  
            start_point_y = 0  
    start_point_x = k  
  
    print("start_point_x, start_point_y_2", start_point_x, start_point_y)  
  
    if ice[start_point_x][start_point_y] == 1:  
        ice_count = ice_count + 1  
         print("ice_count", ice_count)  
    else:  
        pass  
  
print(ice_count)

b. 두번째 트라이 - 성공


# n, m = list(map(int, input().split()))  
ice = []  
result = 0  
  
n, m = 15, 14  
z =['00000111100000',  
 '11111101111110',  
 '11011101101110',  
 '11011101100000',  
 '11011111111111',  
 '11011111111100',  
 '11000000011111',  
 '01111111111111',  
 '00000000011111',  
 '01111111111000',  
 '00011111111000',  
 '00000001111000',  
 '11111111110011',  
 '11100011111111',  
 '11100011111111',]  
  
for i in range(n):  
    ice.append(list(map(int, z[i])))  
  
  
def dfs(x, y, depth, name='main'):  
    print("x, y, way, 깊이 =", x, y, name, depth)  
    depth = depth + 1  
    if x >= 0 and x < n and y >= 0 and y < m:  
        if ice[x][y] == 0:  
            ice[x][y] = 1  
            print(*ice, sep='\n')  
            dfs(x, y-1, depth, name='서')  
            dfs(x+1, y, depth, name='남')  
            dfs(x, y+1, depth, name='동')  
            dfs(x-1, y, depth, name='북')  
  
            return True  
        else:  
            return False  
    else:  
        return False  
  
  
for j in range(n):  
    for k in range(m):  
        if dfs(j, k, 1) == True:  
            result = result + 1  
  
print(result)

a. 회고

반성

스택을 사용하여 문제를 해결해야한다는 생각은 들었다. 다만 어떻게 해야 풀리는지는 몰랐다. 그래서 그냥 주먹구구식으로 풀었다.
x축과 y축도 아직은 헷갈리는 것 같다.
시간이 4시간 이상으로 가장 오래 걸렸다.
- 다만, 이 부분은 4시간 동안 해설지를 보지 않고 어떻게든 문제를 해결하고자 머리를 굴렸으니 후회하지 않는다.
- 생각보다 내가 기초를 활용하는 방법에 대해 깊이 생각하지 않았다는 것을 알게 되었다.

결론

포기하지 말고 하자. 그냥 하자. 계속 하자. 하다보면 재밌어진다. 지금도 살짝 재밌다.

C. 문제 해설

이 문제는 DFS로 해결할 수 있다. 얼음을 얼릴 수 있는 공간이 상, 하, 좌, 우로 연결되어 있다고 표현할 수 있으므로 그래프 형태로 모델링 할 수 있다.

특정한 지점의 주변 상, 하, 좌, 우를 살펴본 뒤에 주변 지점 중에서 값이 '0'이면서 아직 방문하지 않은 지점이 있다면 해당 지점을 방문한다.
방문한 지점에서 다시 상, 하, 좌, 우를 살펴보면서 방문을 다시 진행하면, 연결된 모든 지점을 방문할 수 있다.
모든 노드에 위 방법을 반복하여 방문하지 않은 얼음의 수를 센다.