[백준/파이썬] 16724: 피리 부는 사나이

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

16724번: 피리 부는 사나이

문제 요약 : 사람들은 피리 부는 사나이의 피리에 따라 움직인다. 'SAFE ZONE'을 만들면 피리소리를 듣지 못하여 움직이지 않을 수 있다. 최소의 SAFE ZONE의 개수는 ?

 

예제 입력1

3 4
DLLL
DRLU
RRRU

 

예제 출력1

2

 

예제 입력2 (질문 게시판에 있던 반례)

10 10
DRDRRRRRRD
RDRUDUUUUL
URLDLRRRRD
RRRRLRDLUD
DDRLLDULUU
DRULLLRDUU
DULLDDDURU
URLDDDDUUL
DLRLRDUULL
RRULRUUURU

예제 출력2

12

 

 

시도 )

단순히 사이클이 만들어지면 되는거 아냐? 하고 풀었다.

아래 코드로 풀면 1번같은 예제에서는 다 돌아간다.

 

그러나

D

R D

U R L

이와 같은 예시가 있다 치자.(위의 예제 2의 일부분만 가져왔다)

이렇게되면 D R D R L 이 파트만 확인해주고, U 파트는 다른 개수로 쳐진다.

# 피리부는 사나이
N, M = map(int,input().split())
Map = list(list(map(str,input())) for _ in range(N))
visit = list([True]*M for _ in range(N))
answer = 0

def find(x,y):
    global visit
    if visit[x][y] :
        visit[x][y] = False
        if Map[x][y] == 'U':
            find(x-1,y)
        if Map[x][y] == 'D':
            find(x+1,y)
        if Map[x][y] == 'R':
            find(x,y+1)
        if Map[x][y] == 'L':
            find(x,y-1)
    return 1

for i in range(N):
    for j in range(M):
        if visit[i][j] :
            answer += find(i,j)
        else :
            continue
print(answer)

 

📌 풀이 )

코드가 길어져서 direction으로 따로 빼서 index값을 주도록 만들었다.

 

visit -1이면, 방문하지 않았기 때문에 재귀로 해당 사이클을 구해준다. 이때 위의 예시처럼 단순히 True False를 사용하지 않고 idx라는 값을 따로 주었다.(사이클 확인을 위함)

 

만일 visit이 -1이 아니라면, 방문하지 않은 경우인데 이때에는 두가지 경우로 나누어진다.

• idx가 같을 경우 : 현재 찾고있던 사이클이기 때문에 개수를 세어주고 중단한다.
• idx가 다를 경우 : 이미 만들어진 사이클이기 때문에 개수는 세어주지 않고 중단한다.

# 피리부는 사나이
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


print(answer)