음료수 얼려먹기

<문제>

0	0	1	1	0
0	0	0	1	1
1	1	1	1	1
0	0	0	0	0

0 : 구멍이 존재하는 부분 ->상하좌우로 서로 연걸

1 : 칸막이가 존재하는 부분

 

N*M크기의 얼음 틀이 주어졌을때 총 아이스크림의 개수를 구하는 프로그램을 작성하시오. 위와 같은 4*5크기의 얼음틀이 주어졌을 경우 총 3개의 아이스크림이 생성된다.

 

<풀이>

1. 특정지점의 주변 상,하,좌,우를 살펴본뒤 주변지점중에서 값이'0'이면서 아직 방문하지 않은 지점이 있다면 방문한다.(0->1)
2. 방문한 지점에서 다시 상,하,좌,우를 살펴보면서 방문을 다시 진행하면서 연결된 모든 지점 방문(재귀적으로 dfs 호출)
3. 만약 방문 불가능한 지점일 경우이거나 이미 방문한 경우  함수의 반환결과는  False, 그렇지 않으면 함수의 반환결과는 True이다.
4. 방문가능한 특정지점에서 출발해 방문가능한 인접지역을 전부 다 방문하고 방문이 최종적으로 끝났을때 함수의 반환결과가  True가 된다.
5. 그래프의 모든 지점에서 dfs를 수행한후 반환결과가 True인경우의 갯수가 문제의 정답이 된다.

<코드-파이썬>

# 0	0	1	1	0
# 0	0	0	1	1
# 1	1	1	1	1
# 0	0	0	0	0
# 0 : 구멍이 존재하는 부분 ->상하좌우로 서로 연걸
# 1 : 칸막이가 존재하는 부분
# N*M크기의 얼음 틀이 주어졌을때 총 아이스크림의 개수를 구하는 프로그램을 작성하시오. 위와 같은 4*5크기의 얼음틀이 주어졌을 경우 총 3개의 아이스크림이 생성된다.

n,m = map(int,input().split())
graph = []
for _ in range(n):
    graph.append(list(map(int,input().split())))
def dfs(x,y):
    #주어진 범위를 벗어나는 경우 즉시 종료
    if x<=-1 or x>=n or y<=-1 or y>=m:
        return False

    if graph[x][y] == 0: ##아직 방문하지 않은 경우
        graph[x][y] = 1
        dfs(x-1,y)
        dfs(x+1,y)
        dfs(x,y-1)
        dfs(x,y+1)
        return True
    return False
result = 0
for i in range(n):
     for j in range(m):
         if dfs(i,j) == True:
             result+=1
print(result)

※위코드에서  dfs(0,0)을 수행한경우 graph※

1	1	1	1	0
1	1	1	1	1
1	1	1	1	1
0	0	0	0	0

즉 (0,0)에서 출발해 방문가능한 지역을 전부 방문하고 dfs가 최종적으로 True를 반환한다.(<풀이4>)