No. 16929
1. Problem
2. My Solution
- 시작점과 color 의 정보를 계속해서 인지해야함
- dfs 수행할 때 오른쪽 -> 아래 -> 왼쪽 -> 위에 방향으로 수행
- k >= 4 를 만족하고 마지막 종료 지점이 시작점과 동일해야함
- visited 리스트가 좌표마다 초기화 되어야함
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")
3. Learned
- copy() 함수는 얕은 복사
- copy 모듈의 deepcopy() 함수 이용해야함
- 복잡하지 않은 리스트의 복사는 제대로 복사되지만 리스트 내의 리스트가 존재할 경우 원본의 데이터를 가르키게됨
# 리스트 내의 리스트가 존재하는 객체 복사시 원본 객체를 가르키게됨
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
1. Problem
2. My Solution
- DFS 를 수행하여 순환선을 구함
- BFS 를 수행하여 각 노드에서 순환선까지의 최소 거리를 구함
- 노드마다 dfs, 노드마다 bfs 수행 -> 5700ms
- 시작 노드에서 시작해서 다시 시작노드로 돌아오면 싸이클 (해당 경로를 저장하고 있음)
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=' ')
3. Others' Solutions
- 한 노드에서의 dfs 수행, 순환선의 끝에서 bfs 수행 -> 108ms
- 방문했던 노드를 또 방문할 때 거리차가 3이상이면 싸이클, 싸이클의 시작을 만나기 전까지 방문했던 노드들을 저장 (return 이용)
- 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=' ')
4. Learned
