[5문제] DFS 문제 풀이 02

백준 2644번

해결 아이디어

'나'부터 깊이 우선 탐색을 실시한다. 탐색을 하면서 '나'가 아니고 방문하지 않았을 경우, 촌수를 더해준다. visited라는 리스트를 만들어서 인덱스 값에 촌수를 저장하도록 하였다.

내가 작성한 코드

import sys
sys.setrecursionlimit(10000)
input = sys.stdin.readline

n = int(input())
a,b = map(int, input().split())
m = int(input())
graph = [[] for _ in range(n+1)]

for i in range(m):
    x,y = map(int, input().split())
    graph[x].append(y)
    graph[y].append(x)

visited = [0] * (n+1)

def dfs(started):
    for i in graph[started]:
        if i != a and not visited[i] :
            visited[i] = visited[started] + 1
            dfs(i)
    
dfs(a)
if visited[b] == 0:
    print(-1)
else:
    print(visited[b])

백준 2667번

해결 아이디어

대각선을 제외한 상하좌우의 이동경로를 설정한다. count라는 변수를 지정해 깊이 우선 탐색시 단지내 아파트에 방문할 때마다 1씩 증가시켜주면서 단지 탐색이 끝날 시 리스트에 넣어준다. 이때 단지를 탐색할 시에는 방문한 아파트는 0으로 지정하여 중복으로 세는 것을 방지한다. 리스트에 넣어준 후, count를 초기화시켜주면서 다음 단지로 이동한다.

내가 작성한 코드

n = int(input())
graph = []
num = []

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

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


def dfs(x, y):
    if x < 0 or x >= n or y < 0 or y >= n:
        return False

    if graph[x][y] == 1:
        global count
        count += 1
        graph[x][y] = 0
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            dfs(nx, ny)
        return True


count = 0

for i in range(n):
    for j in range(n):
        if dfs(i, j) == True:
            num.append(count)
            count = 0

num.sort()
print(len(num))
for i in range(len(num)):
    print(num[i])

백준 2583번

해결 아이디어

다른 문제들처럼 지도나 종이 밖으로 나가지 않도록 하는 조건을 걸어주는 것이 아닌 모눈종이 안에서 방문하지 않은 부분이 있으면 개수를 세어야 한다. 직사각형은 1을 부여하여 영역을 구분하도록 하였다. 타인의 코드를 참고하였다.

코드

import sys
sys.setrecursionlimit(10000)

def dfs(y, x, cnt):
    graph[y][x] = 1
    for dy, dx in d:
        Y, X = y+dy, x+dx
        if (0 <= Y < M) and (0 <= X < N) and graph[Y][X] == 0:
            cnt = dfs(Y, X, cnt+1)
    return cnt
    
M, N, K = map(int, input().split())
graph = [[0]*N for _ in range(M)]
for _ in range(K):
    x1, y1, x2, y2 = map(int, input().split())
    for i in range(y1, y2):
        for j in range(x1, x2):
            graph[i][j] = 1
d = [(-1, 0), (1, 0), (0, -1), (0, 1)]
res = []
for i in range(M):
    for j in range(N):
        if graph[i][j] == 0:
            res.append(dfs(i, j, 1))
print(len(res))
print(*sorted(res))

백준 1926번

해결 아이디어

2583번과 유사한 문제였다. dfs로 문제를 해결했으나, 메모리 초과를 만나게 되었다. 구글링을 통해서 메모리 초과일 경우, bfs로 해결을 한다고 한다. bfs는 학습하기는 했지만, 겉핥기 식으로 한 것 같아서 조금 더 학습해본 후, 문제를 다시 풀어보어야겠다.

내가 작성한 코드

import sys
sys.setrecursionlimit(10**6)

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

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

count = 0
pic= []

def dfs(x,y):
    if x < 0 or x >= n or y < 0 or y >= m:
        return False
    
    if drawing_paper[x][y] == 1:
        global count
        count += 1
        drawing_paper[x][y] = 0
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            dfs(nx, ny)
        return True
    
for i in range(n):
    for j in range(m):
        if drawing_paper[i][j] == 1:
            dfs(i,j)
            pic.append(count)
            count = 0

print(len(pic))

if len(pic) == 0:
    print(0)
else:
    print(max(pic))

백준 2251번

해결 아이디어

물통에서 물을 옮기는 과정은 a -> b, a -> c, b -> a, b -> c, c -> a, c -> b 총 6가지이다. 경우의 수를 고려하여 각 과정에서의 조건을 판단하여 구현한다. a -> b로 물을 옮기는 경우를 예를 들어보자.
A물통과 B물통에 들어 있는 물이 B물통의 용량보다 크다면, B물통에는 용량만큼 물이 들어가게 되고, A물통에는 A물통과 B물통에 들어 있는 물에서 B물통의 용량만큼 빼준 물의 양이 담기게 된다.
반대로 A물통과 B물통에 들어 있는 물이 B물통의 용량보다 작다면, 모든 물이 B물통에 담기게 된다. dfs를 반복하면서 A물통이 0이 되면, True를 찍어준다.

내가 작성한 코드

def dfs(ca, cb, cc):
    if visited[ca][cb] == True:
        return;
 
    if ca == 0:
        ans[cc] = True
 
    visited[ca][cb] = True
 
    # a -> b
    if ca + cb > b:
        dfs((ca + cb) - b, b, cc)
    else:
        dfs(0, ca + cb, cc)

    # b -> a
    if cb + ca > a:
        dfs(a, (cb + ca) - a, cc);
    else:
        dfs(cb + ca, 0, cc)
        
    # c -> a
    if cc + ca > a:
        dfs(a, cb, (cc + ca) - a)
    else: 
        dfs(cc + ca, cb, 0)
        
    # c -> b
    if cc + cb > b:
        dfs(ca, b, (cc + cb) - b)
    else:
        dfs(ca, cc + cb, 0)
        
    # b -> c, a -> c
    # a + b = c 
    dfs(ca, 0, cb + cc)
    dfs(0, cb, ca + cc)
    
ans = [False] *201
visited = [[False for _ in range(201)]for _ in range(201)]

a,b,c = map(int, input().split())

dfs(0,0,c)
for i in range(len(ans)):
    if ans[i] == True:
        print(i, end=" ")