[Python] 백준 코테 연습 - DFS

 

연결 요소의 개수 - 실버2

https://www.acmicpc.net/problem/11724

import sys
sys.setrecursionlimit(10000) # 재귀 최대 깊이 설정
input=sys.stdin.readline

N, M = map(int, input().split())
A = [[] for _ in range(N+1)]  # 그래프 데이터 저장 리스트
visited = [False]*(N+1)

def DFS(v):
    visited[v] = True
    for i in A[v]:
        if not visited[i]:
            DFS(i)

for _ in range(M):
    s, e = map(int, input().split())
    A[s].append(e)
    A[e].append(s)

count = 0

for i in range(1, N+1):
    if not visited[i]:
        count += 1
        DFS(i)

print(count)

• 기본적인 DFS. 재귀 깊이 설정 까먹지 않기..

 

---

DOM - 실버2

https://www.acmicpc.net/problem/10552

import sys
sys.setrecursionlimit(10000) # 재귀 최대 깊이 설정
input=sys.stdin.readline

N, M, P = map(int, input().split())  # 사람 수, TV 채널 수, TV 초기 채널
A = [[] for _ in range(M+1)]
visited = [False]*(M+1)
count = 0

for _ in range(N):
    s, e = map(int, input().split())  # 좋아하는 채널, 싫어하는 채널
    A[e].append(s)  # 단방향


while True:
    visited[P] = True
    if A[P]:
        count += 1
        P = A[P][0]

        if visited[P]:
            count = -1
            break

    else:
        break

print(count)

• DFS를 돌 때 모든 노드가 아닌 첫번째 노드(가장 어린 사람)것만 돌아야 한다.
• 이미 방문한 채널이 또 나오는 경우 무한 루프 이므로 count = -1

 

---

경로 찾기 - 실버 1

https://www.acmicpc.net/problem/11403

import sys
sys.setrecursionlimit(10000) # 재귀 최대 깊이 설정
input=sys.stdin.readline

N = int(input())
A = [list(map(int, input().split())) for _ in range(N)]
visited = [False]*N

def DFS(v):
    for i in range(N):
        if A[v][i] ==1 and visited[i] == 0:
            visited[i] = 1
            DFS(i)

for i in range(N):
    DFS(i)
    for j in range(N):
        if visited[j] == 1:
            print(1, end =' ')
        else:
            print(0, end=' ')
    print()
    visited = [False]*N

• 플로이드-워셜은 익숙하지가 않다...DFS로 풀기
• 문제 이해가 좀 어려웠는데, 그냥 각 노드마다(i) DFS로 방문 가능한 모둔 노드(visited)를 방문 후 출력해준다.
• https://whitehairhan.tistory.com/333

[백준/DFS-BFS] 11403: 경로 찾기 - 파이썬

 

 

 

---

단지번호붙이기 - 실버1

https://www.acmicpc.net/problem/2667

import sys
sys.setrecursionlimit(10000) # 재귀 최대 깊이 설정
input=sys.stdin.readline

N = int(input())
A = [list(map(int, input().rstrip())) for _ in range(N)]
visited = [[0]*N for _ in range(N)]
ans = 0
home_count = []
dx = [0,0,1,-1]
dy = [-1,1,0,0]

def DFS(i,j):
    visited[i][j] = 1
    for k in range(4):
        nx = i + dx[k]
        ny = j + dy[k]

        if nx < 0 or nx > N-1 or ny < 0 or ny > N-1:
            continue

        if A[nx][ny]==1 and visited[nx][ny] == 0:
            visited[nx][ny] = 1
            home_count[ans-1] += 1
            DFS(nx, ny)


for i in range(N):
    for j in range(N):
        if A[i][j] == 1 and visited[i][j] == 0:
            ans += 1
            home_count.append(1)
            DFS(i, j)
            # print(visited)

print(ans)
home_count.sort()
for i in home_count:
    print(i)

 

 

 

---

영역 구하기 - 실버 1

https://www.acmicpc.net/problem/2583

import sys
sys.setrecursionlimit(10000) # 재귀 최대 깊이 설정
input=sys.stdin.readline

M, N, K = map(int, input().split())
visited = [[False]*N for _ in range(M)]


for _ in range(K):
    x1, y1, x2, y2 = map(int, input().split())
    for i in range(x1, x2):
        for j in range(y1, y2):
            visited[j][i] = True
# rint(visited)
ans_list = []
ans = 0

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

def DFS(i,j):
    visited[j][i] = True
    for k in range(4):
        nx = i + dx[k]
        ny = j + dy[k]

        if nx < 0 or nx > N-1 or ny < 0 or ny > M-1:
            continue

        if not visited[ny][nx]:
            visited[ny][nx] = True
            ans_list[ans-1] += 1
            DFS(nx, ny)

for i in range(N):
    for j in range(M):
        if not visited[j][i]:
            ans_list.append(1)
            ans += 1
            DFS(i, j)
            # print(visited)

print(ans)
ans_list.sort()
print(*ans_list)

 

• x, y 좌표 헷갈린당

 

---

적록색약 - 골드5

https://www.acmicpc.net/problem/10026

import sys
sys.setrecursionlimit(10000) # 재귀 최대 깊이 설정
input=sys.stdin.readline

N = int(input())
picture = [input().rstrip() for _ in range(N)]
picture2 = [row.replace('R', 'G') for row in picture]
visited = [[False]*N for _ in range(N)]
visited2 = [[False]*N for _ in range(N)]
color = ''

nx = [0,0,-1,1]
ny = [-1,1,0,0]

def DFS(i, j, color):
    visited[j][i] = True

    for k in range(4):
        dx = i + nx[k]
        dy = j + ny[k]

        if dx < 0 or dx > N-1 or dy <0 or dy > N-1:
            continue

        if not visited[dy][dx] and picture[dy][dx] == color:
            # print(dy, dx, color)
            DFS(dx, dy, color)

def DFS2(i, j, color):
    visited2[j][i] = True

    for k in range(4):
        dx = i + nx[k]
        dy = j + ny[k]

        if dx < 0 or dx > N-1 or dy <0 or dy > N-1:
            continue

        if not visited2[dy][dx] and picture2[dy][dx] == color:
            # print(dy, dx, color)
            DFS2(dx, dy, color)

ans1 = 0
ans2 = 0

for i in range(N):
    for j in range(N):
        if not visited[j][i]:
            # print(i, j, picture[j][i])
            ans1 += 1
            DFS(i, j, picture[j][i])

        if not visited2[j][i]:
            ans2 += 1
            DFS2(i, j, picture2[j][i])

print(ans1, ans2)

• DFS, visited, picture모두 적록색약 버전과 아닌 것으로 따로 나눠서 구현했다.
• 적록색약 버전은 R을 모두 G로 치환했다.

 

 

---

숫자 고르기 - 골드5

https://www.acmicpc.net/problem/2668

import sys
sys.setrecursionlimit(10000) # 재귀 최대 깊이 설정
input=sys.stdin.readline

N = int(input())
num_list = [0]+[int(input()) for _ in range(N)]
result = []

def DFS(v, i):  # 현재 좌표, 시작한 좌표
    visited[v] = True
    w = num_list[v]
    if not visited[w]:
        DFS(w, i)
    elif visited[w] and w==i:
        result.append(w)

for i in range(1, N+1):
    visited = [False]*(N+1)
    DFS(i, i)

print(len(result))
result.sort()
for i in result:
    print(i)

• DFS에서 좌표들을 돌면서 도착한 적 없는 좌표이면 DFS를 돌리고, 도착한 적이 있고 첫째줄과 둘째줄에서 일치하는 경우에 result에 입력한다.
• 집합 내 숫자가 일치하는 경우는, 숫자가 돌면서 같은 장소에 도착하는 것과 같다. 예를 들어, 1 -> 3 -> 1 로 돌아오게 되는 경우 정답 리스트에 넣는다.
• 노드...의 연결을 생각하면 이해가 좀 쉬울 것 같다. 그냥 생각해내기에는 어려웠음...
• https://acupoframen.tistory.com/77

BOJ 2668: 숫자고르기 [Python 3]

 

 

 

---

# 회고

 

마지막 문제가 좀 많이 어려웠다..

DFS 어려워...