피리 부는 사나이 ( 16724 번 )

16724번: 피리 부는 사나이

 

---

🧠 알고리즘

• 사이클 탐지 + 경로 압축 (Cycle Detection with Path Compression)

 

✔️ 동작 방식

• 아직 방문되지 않은 방향 칸을 시작점으로 탐색 시작.
• 현재 칸에서 지정된 방향으로 계속 이동하면서 visit_set에 경로를 저장.
• 이미 처리된 영역으로 도달: 지금까지의 경로 칸들을 같은 번호로 갱신.
• 자기 자신으로 다시 돌아옴 (사이클 발견): 경로 전체에 새로운 num을 부여.
• 최종 모든 사이클의 개수(num) 반환.

---

 

 

🧾 코드

import sys

def _main(n, m):
    map_list = [list(sys.stdin.readline().rstrip()) for _ in range(n)]
    num = 0
    move_dict = {'U': (-1, 0), 'D': (1, 0), 
                 'L': (0, -1), 'R': (0, 1)}
    
    for i in range(n):
        for j in range(m):
            if map_list[i][j] in ('U', 'D', 'L', 'R'):
                x, y = i, j
                visit_set = {(i, j)}
                count = 0

                while True:
                    move_x, move_y = move_dict[map_list[x][y]]
                    next_x, next_y = x + move_x, y + move_y

                    if map_list[next_x][next_y] not in ('U', 'D', 'L', 'R'): # 이미 길이 개척된 경우
                        for go_x, go_y in visit_set:
                            map_list[go_x][go_y] = map_list[next_x][next_y]
                        break
                        
                    if (next_x, next_y) not in visit_set:
                        visit_set.add((next_x, next_y))
                        x, y = next_x, next_y
                    else:
                        for go_x, go_y in visit_set:
                            map_list[go_x][go_y] = num
                        num += 1
                        break

    return num

n, m = map(int, sys.stdin.readline().rstrip().split())
print(_main(n, m))

---

 

 

⏱️ 시간 복잡도

for i in range(n) : 이차형 리스트를 탐색하며 경로 압축 ( 이차형 시간 복잡도 )
    for j in range(m)
    
이미 처리된 경우는 상수 시간으로 바로 종료
해당 알고리즘 시간 복잡도 : 이차형 시간 복잡도 ( O(n ** 2) )