[python] 백준 16724 : 피리 부는 사나이

문제 링크
https://www.acmicpc.net/problem/16724

문제 이해

결국 이 문제는 주어진 입력에서 사이클의 개수를 찾는 문제이다.
SAFE ZONE은 사이클을 형성하고 있는 곳 안에서는 어디에 배치시켜도 상관없다.

주어진 예제의 경우, 이런식으로 사이클이 총 2개 생기는데, SAFE ZONE 을 꼭 특정한 위치에 만들 필요 없이 해당 사이클 내에서는 어디에 위치시켜도 상관이 없다는 얘기다.

즉, 파란 곳 아무데나 하나, 빨간 곳 아무데나 하나 SAFE ZONE을 만들면 된다.

---

그렇다면 입력이 이렇게 주어진 경우엔 SAFE ZONE 을 어디에 위치시켜야 할까?
위 입력의 답은 1이다.

위와 같이 왼쪽 아래에 있는 사이클 중 한 곳에 SAFE ZONE 을 위치시키면 어느 곳에 있든 SAFE ZONE으로 가게 된다.

풀이

2차원 배열에서 사이클을 찾기 위해 Union-Find 알고리즘을 조금 변형시켰다.

def union(nxt: tuple, cur: tuple):
   nxt_root = find(nxt[0], nxt[1])
   cur_root = find(cur[0], cur[1])
   root[cur_root[0]][cur_root[1]] = nxt_root


def find(i, j):
   if (i, j) == root[i][j]:
       return (i, j)
   root[i][j] = find(root[i][j][0], root[i][j][1])
   return root[i][j]

그냥 이차원 배열로 한 것 뿐이니 이해에 큰 무리는 없었다.
union을 할 때 다음 위치에 union 시킨다.

def dfs(y, x):
    visit[y][x] = 1
    ny, nx = y, x
    if board[y][x] == "U":
        ny -= 1
    elif board[y][x] == "D":
        ny += 1
    elif board[y][x] == "L":
        nx -= 1
    elif board[y][x] == "R":
        nx += 1

    next_root = find(ny, nx)
    if next_root == (ny, nx) and board[ny][nx] != "S":  # not a cycle
        union((ny, nx), (y, x))
        dfs(ny, nx)

    else:  # next location is a cycle
        if next_root == (y, x):  # 새 사이클 형성
            board[y][x] = "S"
            global ans
            ans += 1
            return
        else:  # 기존 사이클에 들어가는 경우
            union((ny, nx), (y, x))
            return

다음은 dfs 함수인데, 위에 ny,nx는 그냥 다음 위치를 정해주는 것이다.
next_root는 다음 위치의 root 값을 나타낸다.
만일 next_root의 값이 자기 자신을 가리키고 있다면 둘 중 하나이다.

1. 사이클과 상관없이 그냥 처음 방문하는 위치이거나
2. 사이클의 끝, SAFE ZONE의 위치이거나

만일 1번 경우(next_root가 가리키는 곳이 다음 곳(ny,nx)이고, SAFE ZONE이 아닐 때, 첫 if문에 해당) 에 해당된다면,
현재 위치(y,x)와 다음 위치(ny,nx)를 union 하고, 다음 위치로 계속 탐색한다.

if next_root == (ny, nx) and board[ny][nx] != "S":  # not a cycle
        union((ny, nx), (y, x))
        dfs(ny, nx)

아닌 경우엔 새 사이클을 형성하는 경우와 기존 사이클에 들어가는 경우로 나뉜다.

else:  # next location is a cycle
        if next_root == (y, x):  # 새 사이클 형성
            board[y][x] = "S"
            global ans
            ans += 1
            return
        else:  # 기존 사이클에 들어가는 경우
            union((ny, nx), (y, x))
            return

next_root가 현재 위치(y,x)를 가리키는 경우일 때 새 사이클을 형성한다.
아니면 기존에 이미 형성되어있던 사이클에 들어가는 경우인데, 이 경우 그냥 현재 위치와 다음 위치를 union 시킨다.

정답 코드

def union(nxt: tuple, cur: tuple):
   nxt_root = find(nxt[0], nxt[1])
   cur_root = find(cur[0], cur[1])
   root[cur_root[0]][cur_root[1]] = nxt_root


def find(i, j):
   if (i, j) == root[i][j]:
       return (i, j)
   root[i][j] = find(root[i][j][0], root[i][j][1])
   return root[i][j]


def dfs(y, x):
   visit[y][x] = 1
   ny, nx = y, x
   if board[y][x] == "U":
       ny -= 1
   elif board[y][x] == "D":
       ny += 1
   elif board[y][x] == "L":
       nx -= 1
   elif board[y][x] == "R":
       nx += 1

   next_root = find(ny, nx)
   if next_root == (ny, nx) and board[ny][nx] != "S":  # not a cycle
       union((ny, nx), (y, x))
       dfs(ny, nx)

   else:  # next location is a cycle
       if next_root == (y, x):  # 새 사이클 형성
           board[y][x] = "S"
           global ans
           ans += 1
           return
       else:  # 기존 사이클에 들어가는 경우
           union((ny, nx), (y, x))
           return


n, m = map(int, input().split())
board = [[] for _ in range(n)]
visit = [[0 for _ in range(m)] for _ in range(n)]
root = [[(i, j) for j in range(m)] for i in range(n)]
for i in range(n):
   board[i] = list(input())

ans = 0
for i in range(n):
   for j in range(m):
       if visit[i][j]:
           continue
       dfs(i, j)
print(ans)