https://www.acmicpc.net/problem/16929
16929번: Two Dots첫째 줄에 게임판의 크기 N, M이 주어진다. 둘째 줄부터 N개의 줄에 게임판의 상태가 주어진다. 게임판은 모두 점으로 가득차 있고, 게임판의 상태는 점의 색을 의미한다. 점의 색은 알파벳 대문www.acmicpc.net
사이클이 있는지를 확인하는 문제
처음엔, 진짜 무식한 방식으로 접근했다.
arr의 모든 점에 대하여 dfs 탐색을 하는데, “깊이가 2 를 넘은 상태에서, 원래의 점과 만나는 경우” 를 성공조건으로 삼았다.
답은 맞게 나왔는데, 시간이 100ms넘게 걸렸다.
그 후, 다시 생각을 해보니,
어느 점에서 dfs를 진행하던간에 만일 이미 방문한 점과 만난다면, 사이클이 존재하는 것이다.
문제는 a->b->a 처럼 그냥 제자리를 도는 경우인데, 이를 해결하기 위하여 이전 dfs의 시작점을 함수에 넣고,
만일 이 dfs함수의 다음 진행점이
“같은 색깔이고, 방문했으며, arr의 크기를 벗어나지 않고, 이전 방문지점이 아니면” 성공이도록 했다.
이러니 시간이 70초대까지 줄어들었다.
여기서 굳이 방문한 위치를 다시 지워줄필요가 없다고 깨닫고, 배열에서 초기 시작점을 탐색할 때 방문하지 않은
지점만 탐색했더니, 마지막으로 72초대가 나왔다.
난진짜빡대가리인듯 ㅋㅋㅋㅋㅋㅋㅋ
##코드(마지막)##
import sysinput =sys.stdin.readlinemoves=[(-1,0),(1,0),(0,-1),(0,1)]
def dfs(i,j,c,last_i=None,last_j=None,depth=1): for a,b in moves:
tmp_i=i+a tmp_j=j+b if depth>3:
if 0<=tmp_i<n and 0<=tmp_j<m and arr[tmp_i][tmp_j]==c and visited[tmp_i][tmp_j] and (tmp_i != last_i or tmp_j !=last_j):
print("Yes") exit()
if 0<=tmp_i<n and 0<=tmp_j<m and c==arr[tmp_i][tmp_j] and not visited[tmp_i][tmp_j]:
visited[tmp_i][tmp_j]=True
dfs(tmp_i,tmp_j,c,last_i=i,last_j=j,depth= depth+1)
returnn,m=map(int,input().split())
arr=[list(input().strip())for _ in range(n)]
visited=[[False for _ in range(m)]for _ in range(n)]c_list=[]for i in range(n):
for j in range(m): if not visited[i][j]:
visited[i][j]=True dfs(i,j,c=arr[i][j])
print('No')