[백준/Python] 16724번(DFS)_피리 부는 사나이

📌문제 유형

자료 구조, 그래프 이론, 그래프 탐색, DFS, 분리 집합 (골드 3)

 

📌문제

16724번: 피리 부는 사나이

 

📌나의 문제풀이

- 길은 같지 않지만, 이전에 만들어둔 safe zone이랑 겹칠 수 있음

• 예) RRLLLLL  -> RR*LLLL 지나가는 경로는 다르지만 *만 겹칠 수 있음

- 상단 내용 참고하여 pass_road(현재 지나간 길)에 있으면 cnt에 1 더하고, pass_road에 없으면 cnt에 0 더함

• pass_road에 있으면 새로운 safe zone 만들어야 하기 때문
• pass_road에 없으면 이전 safe zone과 겹침

- 기본적으로 이미 지나간 길은 visited 처리

n,m = map(int,input().split())

maps = []
for _ in range(n):
    row = list(map(str,input()))
    maps.append(row)

def dfs(x,y):
    
    dir = {'U':[-1,0], 'D' : [1,0], 'L' : [0,-1], 'R' : [0,1]}
    
    # dir 위치 이동
    nx = x + dir[maps[x][y]][0]
    ny = y + dir[maps[x][y]][1]
    
    # 현재 리스트에 있는 것 or 리스트에 없는 것 구분
    if (nx, ny) in pass_road and visited[nx][ny] == 1:   # 더해야 하는 것
        return 1
    elif (nx, ny) not in pass_road and visited[nx][ny] == 1:
        return 0

    if 0 <= nx < n and 0 <= ny < m and visited[nx][ny] == 0:
        visited[nx][ny] = 1
        pass_road.append((nx,ny))
        return dfs(nx,ny)

cnt = 0
visited = [[0 for _ in range(m)] for _ in range(n)] # 현재 방문 체크

for a in range(n):
    for b in range(m):
        
        if visited[a][b] == 0:
            visited[a][b] = 1
            pass_road = [(a,b)]
            ans = dfs(a,b)
            cnt += ans


print(cnt)

 

📌다른사람의 문제풀이

- 유사한 방법으로 접근

# 피리부는 사나이
N, M = map(int,input().split())
Map = list(list(map(str,input())) for _ in range(N))

visit = [[-1 for _ in range(M)] for _ in range(N)]

direction = ['L','R','U','D']
dx = [0,0,-1,1]
dy = [-1,1,0,0]

def move(x,y,idx):
    global answer
    if visit[x][y] != -1:   # 방문함
        if visit[x][y] == idx:
            answer += 1
        return  # 만일 형성된 사이클에 방문하더라도 idx가 다르기때문에 괜찮다

    visit[x][y] = idx
    i = direction.index(Map[x][y])
    move(x + dx[i], y + dy[i], idx)

idx = 0
answer = 0
for n in range(N):
    for m in range(M):
        move(n,m,idx)
        idx += 1

 

📌리뷰

- 문제 해결하는 반례 제공

글 읽기 - 도저히 모르겠습니다.. 반례좀 주시면 감사하겠습니다. python

- 어떠한 방식으로 DFS 응용할 수 있는지 고려