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로 해결할 수 있다. 얼음을 얼릴 수 있는 공간이 상, 하, 좌, 우로 연결되어 있다고 표현할 수 있으므로 그래프 형태로 모델링 할 수 있다.
- 특정한 지점의 주변 상, 하, 좌, 우를 살펴본 뒤에 주변 지점 중에서 값이 '0'이면서 아직 방문하지 않은 지점이 있다면 해당 지점을 방문한다.
- 방문한 지점에서 다시 상, 하, 좌, 우를 살펴보면서 방문을 다시 진행하면, 연결된 모든 지점을 방문할 수 있다.
- 모든 노드에 위 방법을 반복하여 방문하지 않은 얼음의 수를 센다.
a. 책 답안
python-for-coding-test/10.py at master · ndb796/python-for-coding-test (github.com)
참고문헌
나동빈, "이것이 취업을 위한 코딩 테스트다 with 파이썬", 초판, 2쇄, 한빛미디어, 2020년
#코딩테스트 #파이썬 #나동빈 #한빛미디어 #문제 #풀이 #DFS #음료수얼려먹기