[백준 16724번] 피리 부는 사나이(파이썬)

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

16724번: 피리 부는 사나이

이 문제는 '사이클'을 찾는 문제.

이 문제를 풀 때 처음에 드는 생각은

'시작점이 다시 만나면 사이클로 본다'

입니다.

그런데, 이렇게 생각하면

이런 반례가 생깁니다. 

이렇게 사이클이 완성은 되는데

시작점으로 돌아오지 않는 케이스도 생깁니다.

 

이 부분까지 고려해서 수정했던 코드입니다.

#백준 16724번 피리부는 사나이

N,M=map(int,input().split())
room=[list(input())for _ in range(N)]
visited=[[False]*M for _ in range(N)]
answer=0

def dfs(x,y):
    global tmp
    global answer
    global cycle
    for i in range(len(cycle)):
        if (x,y) in cycle[i]:

            for px,py in tmp:
                cycle[i].add((px,py))
            return


    if (x,y) in tmp:
        answer+=1
        return
    else:
        tmp.add((x,y))
        visited[x][y]=True
    if room[x][y]=='D':
        dfs(x+1,y)
    elif room[x][y]=='U':
        dfs(x-1,y)
    elif room[x][y]=='L':
        dfs(x,y-1)
    elif room[x][y]=='R':
        dfs(x,y+1)
    return
cycle=[]

def check(x,y):
    global cycle
    for i in range(len(cycle)):
        if (x,y) in cycle[i]:
            return False
    return True
for x in range(N):
    for y in range(M):
        if check(x,y) and visited[x][y]==False:
            tmp=set()
            visited[x][y]=True
            dfs(x,y)
            cycle.append(tmp)


print(answer)

 

이 코드는 이미 만들어진 사이클에 들어올 때,

현재의 사이클을 해당 사이클로 편입시키는 걸 넣었습니다.

하지만 이 코드는 pypy3로도 시간초과가 떴습니다.

아마, cycle이라는set으로 이뤄진 리스트를 계속 점검해야하고

이후에 tmp set안에 좌표들을 편입시키는 작업을 하면서

for문이 많아져서 시간초과가 생긴듯 합니다.

그래서 이 문제를 visited로 지혜롭게 해결했습니다.

#백준 16724번 피리부는 사나이

N,M=map(int,input().split())
room=[list(input())for _ in range(N)]
visited=[[0]*M for _ in range(N)]


def dfs(x,y,c):
    global tmp
    global cnt
    #현재 사이클을 만나는 경우
    if visited[x][y]==c:
        cnt+=1
        return
    #이미 완성된 사이클을 만나는 경우-->그 사이클에 현재 사이클을 추가해준다
    elif visited[x][y]!=0 and visited[x][y]!=c:
        im=visited[x][y]
        for px,py in tmp:
            visited[px][py]=im
        return
    #아직 방문하지 않은 지역
    elif visited[x][y]==0:
        tmp.append((x,y))
        visited[x][y]=c


    if room[x][y]=='D':
        dfs(x+1,y,c)
    elif room[x][y]=='U':
        dfs(x-1,y,c)
    elif room[x][y]=='L':
        dfs(x,y-1,c)
    elif room[x][y]=='R':
        dfs(x,y+1,c)
    return


cnt=1
for x in range(N):
    for y in range(M):
        if visited[x][y]==0:
            tmp=[]
            dfs(x,y,cnt)


print(cnt-1)

이렇게 구성하면

상대적으로 계산시간이 줄어들어서

시간초과가 뜨지 않고 정답을 맞출 수 있습니다.

사이클을 어떻게 구현할지에 대한 공부와 함께

어떻게 시간초과를 막을 수 있을지 생각하게 만들어준 

좋은 문제입니다. 

(사이클 관련 문제는 처음에 접하면 많이 까다로워서

이렇게 문제로 정리해두면 편할 것 같네요)