3W.2D- 이코테 (DFS & BFS),백준 (순열 사이클)

✏️문제 [음료수 얼려먹기]

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

입력
4 5
00110
00011
11111
00000

---

출력
3

1. 0(구멍이 뚫려있는 부분)을 찾으면 함수 dfs는 True 반환.
2. 뚫려있고 연결되어 있는 0을 1로 만들고 True 반환.
3. 얼음틀 범위를 벗어나면 False 반환.
4. 탐색한 부분이 0이 아닌 칸막이 부분이면 False 반환.
5. dfs에서 리턴된 True인 개수를 카운트.

code

n,m=map(int,input().split())
array=[]
for i in range(n):
    array.append(list(map(int,input())))
def dfs(x,y):
    if -1>=x  or x>=n or -1>=y or y>=m:
        return False
    if array[x][y]==0:
        array[x][y]==1
        dfs(x,y+1) #사진 첨부 참고
        dfs(x,y-1)
        dfs(x+1,y)
        dfs(x-1,y)
        return True
    return False

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

---

✏️문제 [미로 탈출]

<문제>
N x M 크기의 직사각형 형태의 미로에 여러 마리의 괴물이 있어 이를 피해 탈출해야 한다. 현재 위치는 (1, 1)이고 미로의 출구는 (N,M)의 위치에 존재하며 한 번에 한 칸씩 이동할 수 있다. 괴물이 있는 부분은 0으로, 괴물이 없는 부분은 1로 표시되어 있다. 미로는 반드시 탈출할 수 있는 형태로 제시된다. 탈출하기 위해 움직여야 하는 최소 칸의 개수를 구하라. 칸을 셀 때는 시작 칸과 마지막 칸을 모두 포함해서 계산한다.

입력: 첫째 줄에 두 정수 N, M(4 <= N, M <= 200)이 주어진다. 다음 N개의 줄에는 각각 M개의 정수(0혹은 1)로 미로의 정보가 주어진다. 각각의 수들은 공백 없이붙어서 입력으로 제시된다. 또한 시작 칸과 마지막 칸은 항상 1이다.
출력: 첫째 줄에 최소 이동 칸의 개수를 출력한다.

입력 예시

5 6
101010
111111
000001
111111
111111

출력 예시
10

code

from collections import deque
n, m = map(int, input().split())
graph = []

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

dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

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

    while queue:
        x, y = queue.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if nx < 0 or ny < 0 or nx >= n or ny >= m:
                continue            
            if graph[nx][ny] == 0:
                continue    
            if graph[nx][ny] == 1:
                graph[nx][ny] = graph[x][y] + 1
                queue.append((nx, ny))
                if nx == n -1 and ny == m -1:
                    return graph[n - 1][m - 1]                
    return graph[n - 1][m - 1]
    
print(bfs(0,0))

DFS & BFS 문제를 거의 처음 풀다보니 푸는 시간도 오래걸리고 막힐때 해답을 봐도 이해하는데 시간이 꽤 걸린다..흑흑

---

✏️백준 [ 순열 사이클 ]

code

import sys
sys.setrecursionlimit(2000)
def dfs(i):
    visited[i]=True
    Next_Path=Path[i]
    if not visited[Next_Path]:
        dfs(Next_Path)

Test=int(input())
for _ in range(Test):
    n=int(input()) #순열의 크기
    Path= [0]+list(map(int, input().split())) #경로 공백 구분
    visited=[True]+[False]*n
    cnt=0
    for j in range(1,n+1):
        if not visited[i]:
            dfs(i)
            cnt=cnt+1
    print(cnt)

참고 블로그: https://claude-u.tistory.com/434

블로그를 참고해서 작성했는데도 오류가 계속난다....오늘은 오류를 못찾겠다..