백준 16929번 Two Dots 파이썬

 

16929번: Two Dots

문제풀이

핵심

1. 사이클을 만족하는 조건은 점이 같은 색이고 4개이상으로 이루어져있으며, 처음 시작한 점에서 돌아온 점이 일치하는지 여부
2. 파고 들어가서 검사하고 또 검사하는 dfs 문제

나는 여기서 잘 생각을 못했던 부분은, 사이클 만족 조건을 제대로 지키지 않았다는 것.. 사이클인지 어떻게 확인하지? (매개변수로 count + 1씩해서 4개인지 확인 하면 되지), 돌아와서 같은 점인지 어떻게 확인할까?( 상하좌우 좌표 이동하면서 출발 좌표랑 같은지 확인하면 되지 즉, 처음 시작 좌표를 저장하고 있어야한다.)

새로 변수를 사용한다고 해서 하늘이 무너지는 것이 아닌데,,!! 변수 잘 활용합시다.

코드

def dfs(color, x, y, start_x, start_y, cnt):
    visited[x][y] = 1
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        # 상하좌우 검사 후, 벽을 만날시 continue
        if nx < 0 or nx >=n or ny < 0 or ny >= m:
            continue
        # 상하좌우 체크 후, 만약 처음 시작한 점의 좌표와 같고 이미 4개이상의 점이라면! 사이클 존재.
        # 더이상 찾을 필요 없으므로, exit
        if nx == start_x and ny == start_y and cnt >= 4:
            print('Yes')
            exit()
        # 만약 방문하지 않았고, 현재 위치에서 같은 색이라면, 사이클로 포함. 개수 증가.
        if visited[nx][ny] == 0 and g[nx][ny] == color:
            dfs(color, nx, ny, start_x, start_y, cnt + 1)


n, m = map(int, input().split())
g = []
for _ in range(n):
    g.append(list(input()))
ans = 'No'
dx = [-1,1,0,0]
dy = [0,0, -1,1]

for i in range(n):
    for j in range(m):
    	# 한 점에서 싸이클 검사 시작하고 난후, 다시 방문 여부 배열 초기화.
        visited = [[0]* m for _ in range(n)]
        # 사이클 첫 점의 색, x, y 좌표와 처음 시작한 점의 좌표, 사이클 점 개수를 저장할 cnt.
        dfs(g[i][j], i, j, i, j, 1)
print(ans)