[BOJ] 16929. Two Dots(Python) / DFS

16929번: Two Dots

게임판의 상태가 주어졌을 때, 사이클이 존재하는지 아닌지 구하는 문제다.

# 23분 소요

• 사용 알고리즘 : DFS 깊이 우선 탐색
• 설명할 것이 없는 듯.. 아래 코드와 같이 모든 정점에서 dfs를 돌리며 재귀로 갈 수 있는 곳으로 나아간다.
• 격자 밖이거나 이동할 곳의 문자가 다르다면 continue
• 방문할 수 있는 곳에만 방문 표시하며 재귀로 나아가고 출발지에 다다르고, 이동 횟수가 4번 이상이면 "Yes"를 출력하고 종료한다.
• 모든 재귀가 끝나도 사이클 이룰 수 없다면 "No"를 출력한다.

 

두 개의 코드를 첨부할 것이다. 우선, 나의 코드이다.

파이썬 코드는 다음과 같다.

---

from sys import stdin
input = stdin.readline

dr = (1, 0, -1, 0)
dc = (0, 1, 0, -1)

def dfs(depth, r, c, char, gr, gc):
    if (r, c) == (gr, gc) and depth >= 4:
        print("Yes")
        exit()

    for d in range(4):
        nr = r + dr[d]
        nc = c + dc[d]
        # 격자 밖이거나 다른 문자이면
        if not (0 <= nr < R and 0 <= nc < C) or board[nr][nc] != char:
            continue
        # 방문할 수 있다면
        if not check[nr][nc]:
            check[nr][nc] = 1		# 방문 표시
            dfs(depth+1, nr, nc, board[nr][nc], gr, gc)
            check[nr][nc] = 0		# 복원

# main
R, C = map(int, input().split())
board = [list(input().rstrip()) for _ in range(R)]
check = [[0] * C for _ in range(R)]
for sr in range(R):
    for sc in range(C):
        dfs(0, sr, sc, board[sr][sc], sr, sc)
print("No")

---

• 시간 : 300ms / 메모리 : 136876kb
• 고찰 : 이 코드를 제출하고 보니 시간, 메모리가 남들에 비해 많이 소요되더라.. 다른 사람들 코드를 보다 보니 굳이 내 코드처럼 모든 정점에서 다 dfs 돌릴 필요 없이 check배열에서 표시 안 된 곳만 탐색하면 된다. 그리고, 이전 위치와 같은 위치만 아니면 재귀로 나아갈 수 있으므로 일일이 check에 표시했다 지웠다 할 필요가 없다. 설명력이 떨어지는 것 같으니 그냥 코드를 첨부한다. 코드를 보면 이해가 쉬울 것이다! 시간이 1/3 수준으로 줄었다. 메모리 역시 줄일 수 있었다.

---

from sys import stdin
input = stdin.readline

dr = (1, 0, -1, 0)
dc = (0, 1, 0, -1)

def dfs(r, c, char, br, bc):
    if check[r][c]:
        print("Yes")
        exit()
    
    check[r][c] = 1     # 방문 표시
    for d in range(4):
        nr = r + dr[d]
        nc = c + dc[d]
        # 벽이거나 문자 다르면 
        if not (0 <= nr < R and 0 <= nc < C) or board[nr][nc] != char:
            continue
        if (nr, nc) == (br, bc):    # 이전 위치와 같은 위치면 
            continue
        dfs(nr, nc, char, r, c)

# main
R, C = map(int, input().split())
board = [list(input().rstrip()) for _ in range(R)]
check = [[0] * C for _ in range(R)]
for sr in range(R):
    for sc in range(C):
        if not check[sr][sc]:
            dfs(sr, sc, board[sr][sc], -1, -1)
print("No")

---

• 시간 : 124ms / 메모리 : 123388kb