1. 음료수 얼려 먹기

1. N*M 크기의 얼음틀이 있다. 1<= N, M <= 1,000
2. 구멍 뚫려있는 부분 0, 칸막이가 존재하는 부분 1
3. 구멍 뚫려 있는 부분끼리 상, 하, 좌, 우로 붙어 있는 경우 서로 연결되어 있는 것으로 간주.
4. 이 때 얼음 틀의 모양 주어질 때 생성되는 아이스크림 덩어리 개수?

얼음 틀 모양의 예시
00110
00011
11111
00000

이 경우, 총 3개의 아이스크림 덩어리가 만들어진다.

1.1 책 답안

• 못 품
• 마지막 return False를 자꾸 빠트림 주의
• 재귀함수 아직 익숙하지 않음

# DFS같음
n, m = map(int, input().split())

# 2차원 리스트 맵 정보 받기
graph = []
for i in range(n):
  graph.append(list(map(int, input()))) #띄어쓰기 없이도 분리된다?

# DFS로 특정한 노드를 방문한 뒤에 연결된 모든 노드들도 방문
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 k in range(m):
    if dfs(i,k)==True:
      result += 1

print(result)

2. 미로 탈출

1. N*M 크기의 미로가 있다. 4 <= N, M <= 200
2. 현재 위치는 (1,1)이고 한 번에 한 칸씩 움직일 수 있다.
3. 0은 진입 불가하고 1로 표시되어있는 길로만 이동가능.
4. 최단거리는? (시작칸과 마지막은 항상 1이다.)

2.1 내 답안

• 틀린 풀이 : 최단거리는 오른쪽 방향, 아래 방향이 다른 방향보다 우선이라 생각해 dfs로 풀었음. 근데 생각해보니 주어지는 그래프에 따라 위쪽 방향이나 왼쪽 방향으로 가야할 수도 있음.
• 이동 가능할 때마다 현재 좌표 방문처리하고,result += 1했는데 비효율적인것 같다.

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

result = 1 
def dfs(x, y):
  global result
  if x <= -1 or x >= n or y <= -1 or y >= m:
    return False
  if x == (n-1) and y == (m-1):
    return result
  if graph[x][y] == 1:
    graph[x][y] = 1
    result += 1
    print(x,y)
    dfs(x+1, y)
    dfs(x, y+1)

dfs(0,0)
print(result)
  

2.2 책 답안

• 최단거리 문제, 임의의 (x, y) 까지의 최단거리 계속 업데이트
• 현재의 좌표를 queue.popleft()하고 인근 1이 포함된 칸의 좌표를queue.append()
• 이동 하면 그 자리에 계속 1이 더해지므로 if graph[x][y] == 1만으로 처음 방문하는 경우를 찾을 수 있다.

# N, M을 공백으로 구분하여 입력받기
n, m = map(int, input().split())
# 2차원 리스트의 맵 정보 입력받기
graph = []
for _ in range(n):
  graph.append(list(map(int, input())))

from collections import deque

# 이동할 네 방향 정의(상,하,좌,우)
dx = [-1, 1, 0, 0] #상하좌우
dy = [0, 0, -1, 1]

def bfs(x,y):
  # 큐 구현을 위해 deque 라이브러리 사용
  queue = deque()
  queue.append((x, y))

  # 큐가 빌 때까지 반복
  while queue:
    x, y = queue.popleft()
    # 현재 위치에서 네 방향으로의 위치 확인
    for i in range(4):
      new_x = x+dx[i] 
      new_y = y+dy[i]
      # 미로 찾기 공간을 벗어나는 경우 무시
      if new_x <= -1 or new_x >= n or new_y <= -1 or new_y >= m:
        continue
      # 괴물이 있는 경우 무시 -> 이 조건문은 없어도 될 것 같음. 하지만 모든 경우를 다 고려해야함으로 중요..
      if graph[new_x][new_y] == 0:
        continue
      # 해당 노드를 '처음' 방문하는 경우에만 최단거리로 기록
      if graph[new_x][new_y] == 1: 
        graph[new_x][new_y] = graph[x][y] + 1
        queue.append((new_x, new_y)) 
  return graph[n-1][m-1] #가장 오른쪽 아래까지의 최단거리 반환
print(bfs(0,0))