[이코테 # DFS/BFS 2] 음료수 얼려 먹기(DFS), 미로탈출(BFS)

* 음료수 얼려 먹기(p.149)

• DFS
• 시간제한 : 30분

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

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


def dfs(x, y):  # 상하좌우, 현재 위치의 x,y를 입력
    if x <= -1 or x >= n or y <= -1 or y >= m:
        return False
    if case[x][y] == 0:
        case[x][y] = 1
        dfs(x - 1, y)  # 상
        dfs(x + 1, y)  # 하
        dfs(x, y - 1)  # 좌
        dfs(x, y + 1)  # 우
        return True
    return False


# 순서대로 탐색해서 아이스크림의 개수를 센다.
count = 0
for i in range(n):
    for j in range(m):
        if dfs(i, j) == True:
            count += 1

print(count)

• 못 풂.
• 순환 구조를 짜는 게 어려움.
• 구현 전체 구조 분석. 

< dfs함수를 사용하면 count+=1 >
                      <dfs 함수 >
                                        < dfs 사용 성공 =True>
                                                        방문 체크.
                                                        이동한 위치에서 dfs함수 호출

                                        < dfs 사용 실패=False>

*2회차 bfs 풀이

from collections import deque
n,m=map(int,input().split())    #n=row, m=column

graph=[]
visited=[]

for _ in range(n):
    graph.append(list(map(int,input())))
    visited.append([False]*m)

def bfs(x,y):
    queue=deque()
    queue.append([x,y])

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

    visited[y][x]=True

    while queue:
        x,y=queue.popleft()

        for nx,ny in zip(dx,dy):
            nx=x+nx
            ny=y+ny
            if nx<=-1 or nx>=m or ny<=-1 or ny>=n:
                continue
            if graph[ny][nx]==0 and not visited[ny][nx]:
                queue.append((nx,ny))
                visited[ny][nx]=True
    return 1

count=0
#play
for x in range(m):
    for y in range(n):
        if graph[y][x]==0 and not visited[y][x]:
            count+=bfs(x,y)
        
print(count)

#3회차 23.08.18
n,m=map(int,input().split())    # n=row, m=column
arr=[]
for i in range(n):
    arr.append(list(map(int,input())))

def dfs(x,y):
    arr[x][y]=1
    dx=[-1,1,0,0]    # 상,하,좌,우
    dy=[0,0,-1,1]
    for i in range(4):
        nx=x+dx[i]
        ny=y+dy[i]
        if nx<0 or nx>=n or ny<0 or ny>=m:
            continue
        if arr[nx][ny]==0:
            arr[nx][ny]=1
            dfs(nx,ny)

count=0
for x in range(n):
    for y in range(m):
        if arr[x][y]!=1:
            dfs(x,y)
            count+=1
print(count)

 

* 미로 탈출(p.152)

• BFS
• 시간제한 : 30분

from collections import deque

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

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


# bfs 함수
def bfs(x, y):
    queue = deque()
    queue.append((x, y))
    while queue:  # 큐의 사이즈가 0이면 false를 반환한다.
        x, y = queue.popleft()
        for i in range(4):  # 이동 및 큐 삽입
            nx = x + dx[i]
            ny = y + dy[i]
            if nx < 0 or nx >= n or ny < 0 or ny >= m:
                continue
            if maze[nx][ny] == 0:	# 벽인 경우 무시하기 위한 코드인데, 없어도 됨.
                continue
            if maze[nx][ny] == 1:
                maze[nx][ny] = maze[x][y] + 1
                queue.append((nx, ny))
    return maze[n - 1][m - 1]


print(bfs(0, 0))

 

복기:

1. 아이디어 떠올리기가 어려웠다.

2. queue() 문법 미숙. queue.append((x,y)) 과 x,y = queue.popleft() 기억해둘 것

3. 방향이 나오면 dx, dy로 나누어서 생각하는 것 잊지 말것!

 

23.08.09 2회차 못 풂...

23.08.11 3회차 15분. 그러나 자잘한 실수들. 

23.08.18 4회차 15분.