알고리즘 / 자료구조’ 시리즈

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

  • 0
  • 0
0
0

1. 음료수 얼려 먹기

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

A. 문제

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

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

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

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

a. 예를 들면.

4 * 5 얼음 틀.


00110
00011
11111
00000

일때 아이스크림은 총 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로 해결할 수 있다. 얼음을 얼릴 수 있는 공간이 상, 하, 좌, 우로 연결되어 있다고 표현할 수 있으므로 그래프 형태로 모델링 할 수 있다.

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

python-for-coding-test/10.py at master · ndb796/python-for-coding-test (github.com)

참고문헌

나동빈, "이것이 취업을 위한 코딩 테스트다 with 파이썬", 초판, 2쇄, 한빛미디어, 2020년

#코딩테스트 #파이썬 #나동빈 #한빛미디어 #문제 #풀이 #DFS #음료수얼려먹기

0분전
작성된 댓글이 없습니다. 첫 댓글을 달아보세요!
    댓글을 작성하려면 로그인이 필요합니다.