[백준] 16929 : Two Dots / python

1. 문제 설명

16929번: Two Dots

 

문제

Two Dots는 Playdots, Inc.에서 만든 게임이다. 게임의 기초 단계는 크기가 N×M인 게임판 위에서 진행된다.

각각의 칸은 색이 칠해진 공이 하나씩 있다. 이 게임의 핵심은 같은 색으로 이루어진 사이클을 찾는 것이다.

점 k개 d1, d2, ..., dk로 이루어진 사이클의 정의는 아래와 같다.

• 모든 k개의 점은 서로 다르다.
• k는 4보다 크거나 같다.
• 모든 점의 색은 같다.
• 모든 1 ≤ i ≤ k-1에 대해서, di와 di+1은 인접하다. 또, dk와 d1도 인접해야 한다.
  두 점이 인접하다는 것은 각각의 점이 들어있는 칸이 변을 공유한다는 의미이다.

게임판의 상태가 주어졌을 때, 사이클이 존재하는지 아닌지 구해보자.

 

입력

첫째 줄에 게임판의 크기 N, M이 주어진다.
둘째 줄부터 N개의 줄에 게임판의 상태가 주어진다.
게임판은 모두 점으로 가득차 있고, 게임판의 상태는 점의 색을 의미한다.
점의 색은 알파벳 대문자 한 글자이다.

 

출력

사이클이 존재하는 경우에는 "Yes", 없는 경우에는 "No"를 출력한다.

 

2. 풀이 전 계획과 생각

입력의 형식을 파악 후 어떤 식으로 저장할지 생각

• N, M → 게임판의 크기
• game_board → 게임판의 상태

 

구하고자 하는 바

사이클이 존재여부

 

행위의 규칙성, 패턴 파악

사이클이 만들어지려면,

1. 4개 이상의 서로 다른 점으로 구성 되어 있어야 하고,
2. 시작 지점과 끝 지점이 일치해야 한다.
3. 또한, 모든 점의 색이 같아야 한다.

 

필요한 로직

DFS 탐색하는데,

각 칸을 방문할 때, 시작점으로부터의 거리를 기록해서 4이상이면 사이클을 찾았다고 할 수 있다.

 

3. 풀이

N, M = tuple(map(int, input().split()))
game_board = [input() for _ in range(N)]
check = [[False] * M for _ in range(N)]
dist = [[0] * M for _ in range(N)]

def in_range(y, x):
    return 0 <= y < N and 0 <= x < M

def can_go(y, x, color):
    return in_range(y, x) and game_board[y][x] == color

def go(y, x, count, color):
    dys, dxs = [-1, 1, 0, 0], [0, 0, -1, 1]

    if check[y][x]:
        if count - dist[y][x] >= 4:
            return True
        else:
            return False

    check[y][x] = True
    dist[y][x] = count

    for idx in range(4):
        ny, nx = y + dys[idx], x + dxs[idx]
        if can_go(ny, nx, color):
            if go(ny, nx, count + 1, color):
                return True

    return False

for i in range(N):
    for j in range(M):
        if check[i][j]:
            continue

        dist = [[0] * M for _ in range(N)]
        is_cycle = go(i, j, 1, game_board[i][j])

        if is_cycle:
            print('Yes')
            exit()

print('No')

 

4. 풀이 후 알게된 개념과 소감

• Cycle 여부를 판단하기 위해서,
  한번 방문했다면 시작점으로부터 거리가 4이상인지 확인해주어 Cycle여부를 체크해주었다.
• Cycle 여부를 판단해주려면?
  1. Cycle 여부를 판단하기 위해서, DFS탐색을 할 수 있다.
     한 정점을 중복해서 방문했다면, 방문 시작점으로부터 거리가 4이상인지 확인해주어 Cycle 여부를 체크해줄 수 있다.
  2. Union Find 함수 각 간선을 하나씩 확인하며 두 노드의 루트 노드를 확인
     1. 이때, 루트 노드가 다르다면 두 노드에 대해 Union 연산 실행
     2. 루트 노드가 같다면 사이클로 판별 그래프에 포함한 모든 노드에 대해
        위 과정 반복해서 확인해줌으로써 Cycle 여부를 체크해줄 수 있다.