[SWEA 2105] 디저트 카페

접근

사각형을 그리기위해 시작 위치를 기준으로 (1, -1), (1, 1), (-1, 1), (-1, -1)로 순서대로 이동하도록 구현하였다.

DFS로 탐색을 진행하고 범위를 벗어나거나 이미 방문한 카페라면 return을 하고

그렇지 않을 때는 현재 방향을 그대로 이동하거나 방향을 증가시켜 이동한다. 방향을 증가시켜 이동할 때는 (-1, 1)로 이동하다가 (1, 1) 방향에 목적지가 있을 때 방향을 바꾼다. 또한 (1, -1)이거나 (1, 1)일 때는 현재 방향으로도 이동하고 다음 방향으로도 이동할 수 있도록 재귀호출한다.

 

구현

- 주어진 입력을 모두 받은 후에

- board를 탐색하면서 각 위치에서 dfs를 진행한다.

    N = int(input())
    board = [list(map(int, input().split())) for _ in range(N)]

    answer = -1
    dy = [1, 1, -1, -1]
    dx = [-1, 1, 1, -1]

    for y in range(N):
        for x in range(N):
            visited = []
            dfs(y, x, 0, y, x, visited)

    print("#{} {}".format(tc+1, answer))

- 만약 지금까지 방문한 카페의 수가 4 이상이거나 목적지에 도달했을 때 최댓값 비교를 진행한다.

- 그렇지 않을 때는 범위 내에 있고 아직 방문하지 않았을 때 현재 위치의 카페를 visited에 추가하고

- 방향이 0 또는 1일 때 현재 방향을 유지한 채로 전진하거나 방향을 바꿔서 전진하도록 재귀호출을 한다.

- 방향이 2일 때는 좌상위치에 목적지가 있는지 검사하여 있다면 해당 방향으로 변경한다.

- 없다면 방향을 유치한 채로 전진한다.

- 방향이 3일 때는 목적지를 향해 계속해서 전진한다.

def dfs(cy, cx, dir, sy, sx, visited):
    global answer
    if len(visited) > 3 and dir == 3 and cy == sy and cx == sx:
        answer = max(answer, len(visited))
        return

    if not check_range(cy, cx):
        return
    elif board[cy][cx] in visited:
        return
    else:
        visited.append(board[cy][cx])
        if dir == 0 or dir == 1:
            dfs(cy + dy[dir], cx + dx[dir], dir, sy, sx, visited)
            dfs(cy + dy[dir+1], cx + dx[dir+1], dir+1, sy, sx, visited)
        elif dir == 2:
            if cy - sy == cx - sx:
                dfs(cy + dy[dir+1], cx + dx[dir+1], dir+1, sy, sx, visited)
            else:
                dfs(cy + dy[dir], cx + dx[dir], dir, sy, sx, visited)
        else:
            dfs(cy + dy[dir], cx + dx[dir], dir, sy, sx, visited)
        visited.pop()

---

전체 코드

test_case = int(input())

def check_range(y, x):
    return (0 <= y < N) and (0 <= x < N)

def dfs(cy, cx, dir, sy, sx, visited):
    global answer
    if len(visited) > 3 and dir == 3 and cy == sy and cx == sx:
        answer = max(answer, len(visited))
        return

    if not check_range(cy, cx):
        return
    elif board[cy][cx] in visited:
        return
    else:
        visited.append(board[cy][cx])
        if dir == 0 or dir == 1:
            dfs(cy + dy[dir], cx + dx[dir], dir, sy, sx, visited)
            dfs(cy + dy[dir+1], cx + dx[dir+1], dir+1, sy, sx, visited)
        elif dir == 2:
            # 좌상위치 검사
            if cy - sy == cx - sx:
                dfs(cy + dy[dir+1], cx + dx[dir+1], dir+1, sy, sx, visited)
            else:
                dfs(cy + dy[dir], cx + dx[dir], dir, sy, sx, visited)
        else:
            dfs(cy + dy[dir], cx + dx[dir], dir, sy, sx, visited)
        visited.pop()

for tc in range(test_case):
    N = int(input())
    board = [list(map(int, input().split())) for _ in range(N)]

    answer = -1
    dy = [1, 1, -1, -1]
    dx = [-1, 1, 1, -1]

    for y in range(N):
        for x in range(N):
            visited = []
            dfs(y, x, 0, y, x, visited)

    print("#{} {}".format(tc+1, answer))