글 읽기 - 파이썬, 게시판 아무리 찾아봐도 틀린 곳을 모르겠습니다. ㅜ

chocobae 9달 전 0

DFS 함수포맷에서 약간의 변형을 했습니다.

청소나 후진 성공 시, 재귀 안들어가게

1~4번째까진 방향 별 청소 가능한지 검사하고 5번째에는 후진 가능한지 검사

전부 불가능하면 종료되는 함수입니다.

제가 어떤 부분에서 틀렸는지 게시판을 찾아봐도 도무지 모르겠습니다.

도움 부탁드릴게요 ㅠ

# 예제 2번 결과 (visited), 답 57 나왔습니다.

# 0(북) 1(동) 2(남) 3(서)
dy = (-1, 0, 1, 0)
dx = (0, 1, 0, -1)

# y, x 현재좌표, direction 방향, turn 청소한 순서, clean 청소여부
def dfs(y, x, direction, size_y, size_x, turn, clean):
    # 현재 위치 청소
    if clean == 1:
        visited[y][x] = turn
    for cnt in range(5):
        # 반시계 방향 전환, 전진, 청소함
        if cnt < 4:
            direction = (direction + 3) % 4
            ny = y + dy[direction]
            nx = x + dx[direction]
            # 벽인 경우 SKIP
            if nx < 0 or ny < 0 or nx >= size_x or ny >= size_y:
                continue
            if mapping[ny][nx] == 1:
                continue
            # 이미 청소한 경우 SKIP
            if visited[ny][nx] != 0:
                continue
            # 실행
            dfs(ny, nx, direction, size_y, size_x, turn + 1, 1)
            # 1회만 실행 후 재귀 안함
            break
        # 방향 전환 없음, 후진, 청소 안함
        else:
            direction = direction
            ny = y - dy[direction]
            nx = x - dx[direction]
            # 벽인 경우 SKIP
            if nx < 0 or ny < 0 or nx >= size_x or ny >= size_y:
                continue
            if mapping[ny][nx] == 1:
                continue
            # 실행
            dfs(ny, nx, direction, size_y, size_x, turn, 0)
            # 1회만 실행 후 재귀 안함
            break
    return


# 입력
N, M = map(int, input().split(" "))
r, c, d = map(int, input().split(" "))
mapping = [tuple(map(int, input().split())) for _ in range(N)]
visited = [[0 for _ in range(M)] for _ in range(N)]

# dfs
dfs(r, c, d, N, M, 1, 1)

# 출력
print(max(max(visited)))

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

파이썬, 게시판 아무리 찾아봐도 틀린 곳을 모르겠습니다. ㅜ

chocobae 9달 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말