[이코테] 음료수 얼려 먹기

출처: 이것이 취업을 위한 코딩 테스트다 with 파이썬(나동빈)

https://www.youtube.com/watch?v=7C9RgOcvkvo&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC&index=3

 

문제

• N * M 크기의 얼음 틀이 있습니다. 구멍이 뚫려 있는 부분은 0, 칸막이가 존재하는 부분은 1로 표시됩니다. 구멍이 뚫려 있는 부분끼리 상,하,좌,우로  붙어 있는 경우 서로 연결되어 있는 것으로 간주합니다. 얼음 틀의 모양이 주어졌을 때 생성되는 총 아이스크림의 개수를 구하는 프로그램을 작성하세요.

 

문제 조건

• 입력 조건:

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

• 출력 조건: 한 번에 만들 수 있는 아이스크림의 개수를 출력합니다.

---

작성 코드

원래 bfs보다 dfs를 선호하는 편인데 갑자기 bfs로 풀고싶어서 bfs 구현하려다가 좀 애먹었따...

파이썬은 거의 초보이다보니까 이차원 배열을 잘 다룰 줄 몰라서 특히 힘들었다

from collections import deque

#상,하,좌,우
dx = [-1,1,0,0]
dy = [0,0,-1,1]


def bfs(x,y,graph,visited):
  visited[x][y]=True
  q = deque()
  q.append((x,y))

  while q:
    a,b = q.popleft()
    for i in range(4):
      nx = a + dx[i]
      ny = b + dy[i]
      if 1<=nx<=n and 1<=ny<=m and not visited[nx][ny]:
        visited[nx][ny] = True
        if graph[nx][ny]==0:
          q.append((nx,ny))

  return


  
n, m = map(int, input().split())

graph = [[0 for j in range(m+1)] for i in range(n+1)]
visited = [[False for j in range(m+1)] for i in range(n+1)]

#graph에 값 저장
for i in range(n):
  temp = input()
  for j in range(m):
    graph[i+1][j+1] = int(temp[j])
    

#bfs돌리기
cnt = 0
for i in range(1,n+1):
  for j in range(1,m+1):
    if not visited[i][j] and graph[i][j]==0:
      cnt+=1
      bfs(i,j,graph,visited)
      


print(cnt)

 

 

예시 답안 보려고 하는데 예시에서는 dfs로 구현되어있길래

갑자기 dfs로도 혼자 먼저 구현해보고 싶어서 강의 멈춰놓고 dfs로 다시 풀어봤다

def dfs(x,y,graph,visited):
  visited[x][y] = True

  for i in range(4):
    nx = x + dx[i]
    ny = y + dy[i]
    if 1<=nx<=n and 1<=ny<=m and not visited[nx][ny]:
      visited[nx][ny]=True
      if graph[nx][ny] == 0:
        dfs(nx,ny,graph,visited)

  return

 

강의 예시 코드

일단 보자마자 나보다 코드가 엄청 간결한 게 느껴졌다

 

우선 그래프 초기화하는 부분

# n * m 배열 요소 입력받기

n,m = map(int, input().split())

graph=[]
for i in range(n):
	graph.append(list(map(int,input())))

 -나는 0으로 초기화된 (n+1)*(m+1) 크기의 이차원 배열을 먼저 만들어놓고 값을 입력받으며 하나하나 update해주었는데,

 -예시 코드에서는 graph 리스트를 선언만 해놓고 바로 입력받았음

 

방문 여부 체크

 -나는 주어진 배열과 같은 크기의 새로운 이차원배열을 만들어 거기에 방문여부를 체크해가면서 수행했음

 -예시 코드에서는 새로운 배열을 선언하지 않고, 방문가능한 노드를 방문시 값을 1로 바꾸어줌으로써 방문노드를 체크하였고, 리턴값이 True가 되어 최초로 방문처리가 된 경우에는 카운트를 증가시켜주었다.

 

 

내가 작성한 코드에서는 방문 여부 체크 배열을 따로 선언했기 때문에 예시 답안과 비교하면 메모리가 훨씬 많이 필요할 것이다