[Python] DFS 문제 풀이 정리 2

문제 풀이 이어서 하기.

이번에는 골드 문제도 섞어서 도전!

 

---

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

10026번: 적록색약

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

n = int(input())
arr = []
visited = [[False]*n for _ in range(n)]
visited2 = [[False]*n for _ in range(n)]

for _ in range(n):
    arr.append(list(input().rstrip()))

dx = [0,0,-1,1]
dy = [-1,1,0,0]
# print(arr)
def DFS1(x, y): # 적록 색약 X
    visited[y][x] = True
    for i in range(4):
        nx = x+dx[i]
        ny = y+dy[i]
        if (0<=nx<n) and (0<=ny<n) and not visited[ny][nx] and arr[y][x]==arr[ny][nx]:
            # print(nx, ny, x, y)
            DFS1(nx, ny)

def DFS2(x, y): # 적록 색약 O
    visited2[y][x] = True
    for i in range(4):
        nx = x+dx[i]
        ny = y+dy[i]
        if arr[y][x]=='B': # 적록 색약인 경우 R==G이다.
            if 0<=nx<n and 0<=ny<n and not visited2[ny][nx] and arr[y][x]==arr[ny][nx]:
                DFS2(nx, ny)
        else:
            if 0<=nx<n and 0<=ny<n and not visited2[ny][nx] and arr[ny][nx]!='B':
                DFS2(nx, ny)
                
num1 = 0 # 적록 색약 X
num2 = 0 # 적록 색약 O
for i in range(n):
    for j in range(n):
        if not visited[i][j]:
            num1 += 1
            DFS1(j, i)
        if not visited2[i][j]:
            num2 += 1
            DFS2(j, i)

print(num1, num2)

• 적록 색약인 경우 DFS를 따로 만든다. 'R'과 'G'를 같은 것으로 판단하게 한다. 즉, 'B'가 아니면 이동하게 하기!

---

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

1987번: 알파벳

# 내 풀이(틀림)
import sys
sys.setrecursionlimit(10000000) 
input=sys.stdin.readline

r, c = map(int, input().split()) # 세로, 가로(행, 열)
visited = [[False]*c for _ in range(r)] # 방문한 위치 판별
arr= [] # 알파벳 입력받기
visit_al = [] # 방문한 알파벳 판별

for _ in range(r):
    arr.append(list(input().rstrip()))
# print(arr)

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

def DFS(x, y, k): 
    visited[y][x] = True
    for i in range(4):
        nx = x+dx[i]
        ny = y+dy[i]
        print(nx, ny, visit_al, k)
        if (0<=nx<c) and (0<=ny<r) and not visited[ny][nx] and arr[ny][nx] not in visit_al:
            # print(nx, ny, visit_al, k)
            visit_al.append(arr[ny][nx])
            k = DFS(nx, ny, k+1)

    return k

max_num = 0
for i in range(r):
    for j in range(c):
        if not visited[i][j]:
            visit_al = [arr[i][j]]
            max_num = max(max_num, DFS(j, i, 1))

print(max_num)

• 백트래킹 과정이 없어서 틀렸다.
• DFS돌았을 때 답이 아니면 되돌아가서 다른 길로 가야 한다! 예제 3번을 풀 수 없다...ㅜ

import sys
# sys.setrecursionlimit(10000000) 
input=sys.stdin.readline

r, c = map(int, input().split()) # 세로, 가로(행, 열)
arr= [] # 알파벳 입력받기
visit_al = set() # 방문한 알파벳 판별

for _ in range(r):
    arr.append(list(input().rstrip()))
# print(arr)

dx = [0,0,-1,1]
dy = [-1,1,0,0]
max_num = 0
def DFS(x, y, k): 
    global max_num
    max_num = max(max_num, k)
    for i in range(4):
        nx = x+dx[i]
        ny = y+dy[i]
        if (0<=nx<c) and (0<=ny<r) and arr[ny][nx] not in visit_al:
            visit_al.add(arr[ny][nx])
            DFS(nx, ny, k+1)
            visit_al.remove(arr[ny][nx])

visit_al.add(arr[0][0])
DFS(0,0,1)
print(max_num)

• 백트래킹 추가. 좌측 상단에서 시작한다는 날을 못봐서 수정.
• 방문한 위치는 따로 판별 배열은 필요 없다. 어짜피 방문한 알파벳 판별 set() visit_al에 있으므로..
• DFS를 돌고나서 알파벳은 방문 여부를 False로 바꾼다. 여기서는 set()을 이용하여 remove함.
• 이 코드는 Python으로 하면 시간 초과. PyPy로 해야 아슬아슬 통과된다.

---

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

2573번: 빙산

import sys
import copy
sys.setrecursionlimit(10**5) 
input=sys.stdin.readline

n, m = map(int, input().split()) # 세로, 가로(행, 열)
arr= []
visited = [[False]*m for _ in range(n)] 

for _ in range(n):
    arr.append(list(map(int, input().split())))
# print(arr)

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

def zero_num(x, y, m, n): # 주위 0의 개수
    num = 0
    for i in range(4):
        nx = x+dx[i]
        ny = y+dy[i]
        if 0<=nx<m and 0<=ny<n and arr[ny][nx]<1:
            num+=1
    # print(x, y, num)
    return num

def DFS(x, y): 
    visited[y][x] = True
    for i in range(4):
        nx = x+dx[i]
        ny = y+dy[i]
        if (0<=nx<m) and (0<=ny<n) and not visited[ny][nx] and arr[ny][nx]>0:
            new_arr[ny][nx] -= zero_num(nx, ny, m, n)
            DFS(nx, ny)

num = 0
year = 0
while num < 2:
    visited = [[False]*m for _ in range(n)] 
    # year += 1
    num = 0
    new_arr = copy.deepcopy(arr) # 빙산은 한번에 녹아야 한다!
    for i in range(n):
        for j in range(m):
            if not visited[i][j] and arr[i][j]>0:
                num += 1
                visited[i][j]=True
                new_arr[i][j] -= zero_num(j, i, m, n)
                DFS(j, i)
                arr = new_arr

    if num == 0:
        break

    if num>1:
        break
    year += 1

if num==0:
    print(0)
else:
    print(year)

• 일단 빙산 주위 바다(0)의 개수를 세는 zero_num() 함수를 만들어서 얼마나 녹는지 체크.
• 이때 빙산이 녹더라도 arr 배열에 바로 적용하면 안된다. 다음 빙산이 바다로 잘못 체크할 수 있으므로 new_arr을 만들어 정보를 저장하고, DFS가 끝난 후 한번에 적용했다.
• 나머지는...DFS이다. Python은 시간초과 나서 PyPy로 제출했다.

• sys.setrecursionlimit(10**5) 이거는 Recursive error때문에 해줘야함.
• 재귀 + limit + deepcopy 삼종때문에 시간 초과가 난 듯하다.
• 아래 코드가 반복문으로 푼 DFS이다. 

https://velog.io/@e_juhee/python-%EB%B0%B1%EC%A4%80-2573-%EB%B9%99%EC%82%B0-DFS

[python] 백준 2573 :: 빙산 (DFS)

---

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

1068번: 트리

import sys
import copy
sys.setrecursionlimit(10**5) 
input=sys.stdin.readline

n = int(input())
arr = [[]*n for _ in range(n)]
visited = [False]*n
deleted = [] # 삭제된 노드들

num = list(map(int, input().split()))
for i in range(n):
    if num[i] == -1:
        continue
    else:
        arr[num[i]].append(i)

x = int(input())

def DFS(v):
    visited[v]=True
    for i in arr[v]:
        if not visited[i]:
            deleted.append(i)
            DFS(i)

DFS(x)
deleted.append(x)
ans = 0
for i in range(n):
    if not visited[i]:
        if len(arr[i])==0:
            ans+=1
        elif all(k in deleted for k in arr[i]): # arr[i] 에 있는 모든 노드가 삭제됐다면
            ans+=1
# print(deleted)
print(ans)

• 먼저, DFS로 삭제 노드 + 삭제한 노드의 자식 노드들을 모두 돌아서 visited를 체크해준다.
• 또한 삭제된 노드들은 deleted 배열에 따로 추가해주었다. 
• 만약 visited되지 않았을때, 자식 노드가 없다면 답에 +1
• visited되지 않았지만, 자식 노드가 있는 경우 deleted 배열에 모든 자식 노드가 있는지, 즉 자식 노드가 모두 삭제됐는지 판별한 후 ans +1

---

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

9466번: 텀 프로젝트

# 내 풀이
import sys
import copy
sys.setrecursionlimit(10**5) 
input=sys.stdin.readline

def DFS(v):
    visited[v] = True
    team.append(v)
    if not visited[arr[v]]:
        DFS(arr[v])
    else:
        return

n = int(input())
        
for _ in range(n):
    ans = 0
    num = int(input()) # 학생 수
    arr = [0] + list(map(int, input().split()))
    for i in range(1, num+1):
    	visited = [False]*(num+1)
        team = []
        if not visited[i]:
            DFS(i)
        if team[0]!=arr[team[-1]]:
            ans+=1
    print(ans)

• 시간 초과....각 학생마다 계속 visited를 초기화해서 문제가 생긴 것 같다.

import sys
import copy
sys.setrecursionlimit(10**7) 
input=sys.stdin.readline

def DFS(v):
    global ans
    visited[v] = True
    team.append(v)
    if not visited[arr[v]]:
        DFS(arr[v])
    else:
        if arr[v] in team: # 팀을 이룬다면
            ans += team[team.index(arr[v]):]

n = int(input())
        
for _ in range(n):
    ans = []
    num = int(input()) # 학생 수
    arr = [0] + list(map(int, input().split()))
    visited = [False]*(num+1)


    for i in range(1, num+1):
        if not visited[i]:
            team = []
            DFS(i)
    print(num - len(ans))

• visited는 초기화하지 않고, 팀 하나를 찾았다면 찾은 팀은 DFS를 돌리지 않는다.
• DFS를 돌리다가 만약 방문한 번호를 만났을때, 팀을 이룬다면(team에 해당 번호가 있다면) ans에 팀을 이룬 학생들의 번호를 추가한다.
• 총 학생 수에서 팀을 이룬 학생 수를 뺀 값 출력하기.
• ans += team[team.index(arr[v]):] 이게 핵심이다. DFS를 돌린 전체 학생이 사이클을 형성하지 못하더라도 일부 사이클만 찾을 수 있는 코드!

---

# 회고

 

힘들구만...

골드부터는 시간/메모리를 신경써야 하는 문제가 나온다.

Python으로 할거면 최대한 시간 안잡아먹게 작성하거나, 반복문을 이용해 DFS를 구현하거나, 최대 Recursive 설정을 잘하기. 최후의 방법으로는 PyPy쓰기...