[DFS & BFS] 음료수 얼려먹기 + 2차원 리스트 생성 및 입력 방법

2차원 리스트 생성 및 입력 방법

0. 0으로 채워진 2차원 리스트 생성하기

my_list = [[0 for _ in range(n)] for _ in range(0)]  #0으로 이루어진 2차원 리스트 생성

* for 문에서 _는 변수 지정 없이 반복할 때 사용한다.

 

1. 0으로 채워진 1차원 리스트의 각 원소에 리스트 추가하기

n, m = map(int, input().split()) #n은 행, m은 열
my_list = [0 for _ in range(n)]	#0으로 채워진 1차원 리스트 my_list를 생성함
for i in range(n)
	my_list[i] = list(map(int, input().split()))	#1차원 리스트의 각 원소에 배열을 입력받음

 

2. 빈 1차원 리스트의 각 원소에 리스트 추가하기

n, m = map(int, input().split()) #n은 행, m은 열
my_list = []
for i in range(n):
	my_list.append(list(map(int, input().split())))

append() 메서드를 통해 각 원소에 리스트를 추가한다.

 

3. 선언과 동시에 입력받기

n, m = map(int, input().split()) #n은 행, m은 열
my_list = [list(map(int, input().split())) for _ in range(n)]

---

n, m = map(int, input().split())
ice_frame = [list(map(int, input().split())) for _ in range(n)]

count = 0

def dfs(x,y):
  if x >= n or y >= m or x <= -1 or y <= -1:
    return False
  if ice_frame[x][y] == 0:
    ice_frame[x][y] = 1
    dfs(x-1, y)
    dfs(x+1, y)
    dfs(x, y-1)
    dfs(x, y+1)
    return True
  return False

for i in range(n):
  for j in range(m):
    if dfs(i,j) == True:
      count += 1
print(count)

 

아직 dfs, bfs를 활용을 잘 못해서 코드를 많이 참고했다. 참고하면서 깨달은 점은

사이클을 확인해야한다면 DFS

최단거리(경로)를 확인해야한다면 BFS

 - DFS는 한 노드를 기준으로 깊이를 우선적으로 탐색하기 때문에 사이클을 확인할 수 있음. 반면, 목적지가 아닌 트리여도 말단노드까지 탐색하기 때문에  최단 거리를 보장할 수 없음.  

 - BFS는 한 노드의 모든 인접 노드를 탐색해가며 모든 경로의 거리를 1씩 늘려가며 최단 경로 및 최단거리를 계산하는데 효과적임. 반면, 이미 방문한 정점을 다시 방문하지 않기 때문에 사이클은 찾기 힘듦.

 

---

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

42:46 초에 나오는 문제 풀이입니다.

---

강의 보면서 필기한 것들!