[문제실습] Ch 5. BFS/DFS

1. 음료수 얼려먹기

: 단순하게 0인 부분을 채우고, 채워진 0 부분이 몇 개인지 출력하면 되는 문제이다.

'''
input:
4 5 
00110
00011
11111
00000
output: 3

input:
5 7
1010101
0101010
1111000
0100111
0110000
output: 8

input:
4 5
10001
00000
00000
10001
output: 1
'''

1) BFS

from collections import deque
dpos = [(0, 1), (-1, 0), (0, -1), (1, 0)]

def __main__():
    N, M = map(int, input().split())

    ice_tray = [0 for _ in range(N)]
    for i in range(N):
        ice_tray[i] = list(map(int, input()))
    
    ''' another way
    ice_tray = []
    for i in range(N):
        ice_tray.append(list(map(int, input())))
    '''

    visit = [[0 for col in range(M)] for row in range(N)]
    cnt = 0
    que = deque()

    for i in range(N):
        for j in range(M):
            if visit[i][j] or ice_tray[i][j]:
                continue
            que.append((i, j))
            visit[i][j]=1
            cnt += 1
            while que:
                x, y = que.popleft()
                for dx,dy in dpos:
                    nx, ny = x + dx, y + dy
                    if nx < 0 or nx >= N or ny < 0 or ny >= M or visit[nx][ny]:
                        continue
                    visit[nx][ny] = 1

                    if ice_tray[nx][ny] == 0:
                      que.append((nx,ny))

    return  print("output >>", cnt) 

__main__()

나의 실수> 우선 input에서 input().split()을 사용하면 배열에 제대로 채워지지 않는다. (이건 왜 안 되는지 모르겠다..)

 

2) DFS

dpos = [(0,1),(1,0),(0,-1),(-1,0)]

def DFS(x, y):
    global N, M, ice_tray, visit

    for dx, dy in dpos:
        nx, ny = x + dx, y + dy
        if nx < 0 or nx >= N or ny < 0 or ny >= M or visit[nx][ny] == 1:
            continue

        visit[nx][ny] = 1
        if ice_tray[nx][ny] == 0:
            DFS(nx, ny)

전역변수로 사용하기 위해서 global 키워드를 사용했다.

def __main__():
    global N, M, ice_tray, visit

    N, M = map(int, input().split())

    ice_tray = [0 for _ in range(N)]
    for row in range(N):
        ice_tray[row] = list(map(int, input()))

    visit = [[0 for _ in range(M)] for _ in range(N)]

    cnt = 0
    for i in range(N):
        for j in range(M):
            if ice_tray[i][j] == 1 or visit[i][j] == 1:
                continue
            visit[i][j] = 1
            DFS(i,j)
            cnt += 1
    print("output >> ", cnt)
    return 0

__main__()

 

2. 미로 탈출
: 미로에서 탈출 가능한 최단 경로의 길이를 출력하면 된다.

''' 
input:
5 6
101010
111111
000001
111111
111111
output: 10

input:
5 10 
1001100011
1001110100
1111010111
1010010101
1110111101
output: 20
'''

1) BFS

: BFS는 너비 우선 탐색이기 때문에 찾은 값이 최소 거리일 수 밖에 없다.

from collections import deque
dpos = [(0, 1), (-1, 0), (0, -1), (1, 0)]

def BFS(x,y,r):
  global N, M, maze, visit
  visit[x][y]=1
  que = deque()
  que.append((x,y,r))
  while que:
      x,y,r = que.popleft()
      for dx,dy in dpos:
        nx, ny, nr = x + dx,y + dy, r+1
        if nx < 0 or nx >= N or ny < 0 or ny >= M or visit[nx][ny]:
          continue
        if nx == N-1 and ny == M-1:
          return nr

        visit[nx][ny] = 1
        if maze[nx][ny] == 1:
          que.append((nx, ny, nr))

def __main__():
    global N, M, maze, visit

    N, M = map(int, input().split())
    maze = [0 for _ in range(N)]
    for i in range(N):
        maze[i] = list(map(int, input()))
    visit = [[0 for col in range(M)] for row in range(N)]

    return print("output >>", BFS(0, 0, 1))
  
__main__()

2) DFS

: DFS는 깊이 우선 탐색이므로 출구에 도착했을 때 계산한 경로들 중에 제일 작은 값을 찾아서 출력해야한다.

dpos = [(0, 1), (-1, 0), (0, -1), (1, 0)]

def DFS(x,y,cnt):
  global N, M, mincnt
  if x == N-1 and y == M-1:
    if mincnt > cnt:
      mincnt = cnt
    return cnt

  for dx, dy in dpos:
    nx, ny = x + dx, y + dy
    if nx < 0 or nx >= N or y < 0 or ny >= M or arr[nx][ny] == 0 or visit[nx][ny] == 1:
      continue
    
    if arr[nx][ny] == 1:
      visit[nx][ny] = 1
      DFS(nx, ny, cnt+1)
      visit[nx][ny] = 0

def __main__():
    global N, M, mincnt, arr, visit

    N, M = map(int, input().split())
    mincnt = 201 * 201
    arr = []
    for i in range(N):
        arr.append(list(map(int, input())))

    visit = [[0 for col in range(M)] for row in range(N)]
    visit[0][0] = 1

    DFS(0, 0, 1)

    return print("output >>", mincnt)
  
__main__()

 

BFS와 DFS로 문제를 풀면서 부족했던 점은 조건을 기입할 때 visit과 arr을 사용하는 것에 혼동하는 경우가 있는 것 같다.

주의해야 할 것 같다!

 

github.com/katherine4191/This-is-a-coding-test/tree/master/CH5%20BFS%26DFS

katherine4191/This-is-a-coding-test