이번 문제는 DFS를 통해 사이클의 갯수를 파악하여 해결하는 문제이다. 사이클 당 하나의 선물만 놓아도 구사과는 무조건 그 선물을 받을 수 있기 때문이다. 처음에는 BFS를 통해 사이클을 찾도록 하였다. 그러나 이 방법은 시간초과가 발생하였다.

이에 대한 해결책을 찾아보았고, DFS를 통해 해결할 수 있다는 것을 알게 되었다. cnt변수로 사이클 번호를 부여하고, grid를 DFS를 통해 순회하며 아직 visited의 값이 결정되지 않았다면 결정해주고, 재귀호출하여 사이클을 찾도록 하고, 만약 visited가 결정되어있다면 해당 값을 반환하도록 작성하였다. 이 반환값은 결과변수와 비교하여 더 큰 값을 결과변수로 취하도록 하였다.

Code

n, m = map(int, input().split())
grid = [list(str(input())) for _ in range(n)]
dy, dx = [0, 1, 0, -1], [1, 0, -1, 0]
mapping = {'E': 0, 'S': 1, 'W': 2, 'N': 3}
answer = 0
visited = [[0 for _ in range(m)] for _ in range(n)]
def dfs(sy, sx, cnt):
    if visited[sy][sx]:
        return visited[sy][sx]
    visited[sy][sx] = cnt
    d = mapping[grid[sy][sx]]
    ny, nx = sy+dy[d], sx+dx[d]
    visited[sy][sx] = dfs(ny, nx, cnt)
    return visited[sy][sx]
for i in range(n):
    for j in range(m):
        if not visited[i][j]:
            tmp = dfs(i, j, answer+1)
            answer = max(answer, tmp)
print(answer)