BAEKJOON : 16929, 16947

No. 16929

import sys
sys.setrecursionlimit(10**8)

def dfs(x,y,visited,depth):
    global start
    global color
    
    depth += 1
    visited[x][y] = True

    for dx, dy in move:
        nx = x + dx
        ny = y + dy
       
        if 0 <= nx < n and 0 <= ny < m and board[nx][ny] == color:

            # 다음 지점이 k >= 4 를 만족하고 시작점과 동일하다면
            if depth >= 4 and start == (nx,ny):   
                print("Yes")
                exit()
            if visited[nx][ny] == False:
                dfs(nx,ny,visited,depth)

n,m = map(int,sys.stdin.readline().rstrip().split())
board = []
move = [(0,1),(1,0),(0,-1),(-1,0)]

for _ in range(n):
    board.append(list(sys.stdin.readline().rstrip()))

for i in range(n):
    for j in range(m):
        start = (i,j)               # 싸이클의 시작과 종료지점
        color = board[i][j]         # 점의 색
        visited = [[False] * m for _ in range(n)]
        dfs(i,j,visited,0)

print("No")

# 리스트 내의 리스트가 존재하는 객체 복사시 원본 객체를 가르키게됨
original = [[1],[2,3],[4,5,6]]
copy1 = original.copy()

copy1[0][0] = [4]
print(original)
print(copy1)


# 간단한 리스트의 복사는 복사 후 제대로 이용 가능함
original = [1,2,3]
copy1 = original.copy()

copy1[1] = 10
print(original)
print(copy1)

No. 16947

import sys
from collections import deque
sys.setrecursionlimit(10**5)

# 순환선을 구하기 위한 dfs
def dfs(v,route,depth):
    global start
    visited[v] = True
    depth += 1
    route.append(v)

    for u in graph[v]:
        if start == u and depth >= 3:
            cycle.extend(route)

    for u in graph[v]:
        if visited[u] == False:
            dfs(u,route,depth)
            route.pop()

# 순환선까지의 최단 거리를 구하기 위한 bfs
def bfs(v,depth):
    queue = deque()
    visited[v] = True
    queue.append((v,depth))

    while(queue):
        v,depth = queue.popleft()

        for u in graph[v]:
            if u in cycle:
                return depth+1
            if visited[u] == False:
                queue.append((u,depth+1))
                visited[u] = True


n = int(sys.stdin.readline())
graph = [[] for _ in range(n+1)]
cycle = []
res = [0] * (n+1)

# 노선 정보 입력 받기
for _ in range(n):
    a,b = map(int,sys.stdin.readline().rstrip().split())
    graph[a].append(b)
    graph[b].append(a)

# 순환선 구하기 위한 dfs for문
for i in range(1,n+1):
    if cycle:
        break
    
    visited = [False] * (n+1)
    start = i
    dfs(start,[],0)

# 순환선에 속하는 역은 제외
not_cycle = set(i for i in range(1,n+1)) - set(cycle)

# 순환선에 속하지 않는 역에서만 bfs 수행
for i in not_cycle:
    visited = [False] * (n+1)
    res[i] = bfs(i,0)

for i in range(1,n+1):
    print(res[i],end=' ')

BFSを実行して最短距離を求めると、経路内のノードは自動的に累積して距離を求める

import sys
from collections import deque
sys.setrecursionlimit(10**5)

# 순환선을 구하기 위한 dfs
def dfs(v,depth):

    if check[v]:
        if depth - distance[v] >= 3:
            return v
        else:
            return -1
    
    check[v] = 1
    distance[v] = depth

    for u in graph[v]:
        temp = dfs(u,depth+1)

        if temp != -1:
            check[v] = 2

            if temp == v:
                return -1
            else:
                return temp
    return -1
        

n = int(sys.stdin.readline())
graph = [[] for _ in range(n+1)]
distance = [0] * (n+1)
check = [0] * (n+1)
res = [0] * (n+1)

# 노선 정보 입력 받기
for _ in range(n):
    a,b = map(int,sys.stdin.readline().rstrip().split())
    graph[a].append(b)
    graph[b].append(a)

# 순환선 구하기 위한 dfs 
dfs(1,0)


# 순환선까지 최소 거리를 구하는 bfs
queue = deque()

for i in range(1,n+1):
    if check[i] == 2:
        queue.append(i)
        distance[i] = 0
    else:
        distance[i] = -1

while(queue):
    v = queue.popleft()
    for u in graph[v]:
        if distance[u] == -1:
            queue.append(u)
            distance[u] = distance[v] + 1

for i in range(1,n+1):
    print(distance[i],end=' ')