[백준 16929번] Two Dots - 파이썬

① 문제 링크

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

16929번: Two Dots

 

---

② 알고리즘 분류

그래프 이론, 그래프 탐색, 깊이 우선 탐색

---

③ ★문제풀이 Point★

- 전형적인 DFS 문제

---

④ 풀이

이 문제는 게임판의 상태가 주어졌을 때, 사이클이 존재하는지 아닌지 구하는 문제로 전형적인 DFS 문제다.

사이클이 만들어지는 조건에 대해 살펴보자.

1. 4개 이상의 서로 다른 점으로 구성되어 있어야 함.

2. 시작 지점이 끝 지점과 일치해야 함.

3. 모든 점의 색이 같아야 함.

이제 사이클이 존재하는지 확인하기 위해 dfs 방식을 이용한 cycle 함수를 만들어보자.

• color: 색깔
• x, y: 현재 좌표
• cnt: 점 개수
• start_x, start_y: 시작 좌표

# 사이클이 존재하는지 확인하는 함수
def cycle(color, x, y, cnt, start_x, start_y):
    global ans
    # 이미 사이클을 찾았다면 종료
    if ans is True:
        return
    # 4가지 방향에 대하여
    for i in range(4):
        # 이동 위치 좌표 설정
        nx, ny = x + dx[i], y + dy[i]
        # 이동 위치가 게임판을 벗어나면 건너뛰기
        if nx < 0 or nx >= n or ny < 0 or ny >= m:
            continue
        # 사이클이 존재(4개 이상 점 연결, 처음 시작지점 도달)한다면
        if cnt >= 4 and nx == start_x and ny == start_y:
            # 정답 존재 표시
            ans = True
            return
        # 색깔이 같고 아직 방문하지 않았다면
        if board[nx][ny] == color and visited[nx][ny] == 0:
            # 방문 표시
            visited[nx][ny] = 1
            # 재귀적으로 수행
            cycle(color, nx, ny, cnt + 1, start_x, start_y)
            # 방문 표시 해제
            visited[nx][ny] = 0

 

중요 포인트

1. 만약 점의 개수가 4개 이상(cnt >= 4)이고, 탐색할 좌표(nx, ny)가 시작 좌표(start_x, start_y)와 일치하다면 사이클이 만들어지므로 정답 표시

# 사이클이 존재(4개 이상 점 연결, 처음 시작지점 도달)한다면
if cnt >= 4 and nx == start_x and ny == start_y:
	# 정답 존재 표시
	ans = True
	return

2. 탐색할 좌표의 색깔이 현재 좌표의 색깔과 일치하고 탐색할 좌표를 아직 방문하지 않았다면 DFS 실시

# 색깔이 같고 아직 방문하지 않았다면
if board[nx][ny] == color and visited[nx][ny] == 0:
    # 방문 표시
    visited[nx][ny] = 1
    # 재귀적으로 수행
    cycle(color, nx, ny, cnt + 1, start_x, start_y)
    # 방문 표시 해제
    visited[nx][ny] = 0

3. 이미 사이클이 존재한다면, 굳이 사이클이 있는지 탐색하지 않아도 된다. (시간 단축 POINT!)

# 이미 사이클을 찾았다면 종료
if ans is True:
    return

 

이제 게임을 시작하고, 한 좌표씩 차례대로 cycle 함수를 실행하며 사이클이 존재하는지 확인 game_start()해주면 된다. 

# 게임 시작 함수
def game_start():
    for i in range(n):
        for j in range(m):
            # 사이클 시작 위치 좌표
            start_x, start_y = i, j
            # 방문 표시
            visited[start_x][start_y] = 1
            # 사이클이 존재하는지 함수 실시
            cycle(board[i][j], i, j, 1, start_x, start_y)
            # 사이클이 존재한다면
            if ans:
                return 'Yes'
    # 사이클이 존재하지 않는다면
    return 'No'

 

⑤ 코드

다음 코드는 Python3로 작성하였습니다.

# 16929번 Two Dots

from sys import stdin
input = stdin.readline

# 사이클이 존재하는지 확인하는 함수
def cycle(color, x, y, cnt, start_x, start_y):
    global ans
    # 이미 사이클을 찾았다면 종료
    if ans is True:
        return
    # 4가지 방향에 대하여
    for i in range(4):
        # 이동 위치 좌표 설정
        nx, ny = x + dx[i], y + dy[i]
        # 이동 위치가 게임판을 벗어나면 건너뛰기
        if nx < 0 or nx >= n or ny < 0 or ny >= m:
            continue
        # 사이클이 존재(4개 이상 점 연결, 처음 시작지점 도달)한다면
        if cnt >= 4 and nx == start_x and ny == start_y:
            # 정답 존재 표시
            ans = True
            return
        # 색깔이 같고 아직 방문하지 않았다면
        if board[nx][ny] == color and visited[nx][ny] == 0:
            # 방문 표시
            visited[nx][ny] = 1
            # 재귀적으로 수행
            cycle(color, nx, ny, cnt + 1, start_x, start_y)
            # 방문 표시 해제
            visited[nx][ny] = 0

# 게임 시작 함수
def game_start():
    for i in range(n):
        for j in range(m):
            # 사이클 시작 위치 좌표
            start_x, start_y = i, j
            # 방문 표시
            visited[start_x][start_y] = 1
            # 사이클이 존재하는지 함수 실시
            cycle(board[i][j], i, j, 1, start_x, start_y)
            # 사이클이 존재한다면
            if ans:
                return 'Yes'
    # 사이클이 존재하지 않는다면
    return 'No'

n, m = map(int, input().split())
board = [[a for a in input().rstrip()] for _ in range(n)]
# 방문
visited = [[0] * m for _ in range(n)]
# 동, 남, 서, 북 방향 표시
dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]
# 정답 변수
ans = False

# 정답 출력
print(game_start())

 

16929 파이썬 채점 결과

 

---

 

16929 Two Dots 파이썬