글 읽기 - DFS - 반례까지 알겠는데 어느 부분이 문제인지 모르겠습니다.

park3three 3년 전 0

- 반례

10 10
WWBBWWWBBW
WBBWBWWWWB
WBWBWWBBWW
WBBBBBBBWW
WBBWWWBWWW
WBBBBBWWBB
WWBWWBWWBB
BWWBBWWWBB
BBWBBBBBWB
WWWBBBWWWB

정답: 29

코드: 30

# 안전지역
def is_safe(y, x):
    return -1 < y < 8 and -1 < x < 8 and visited[y][x] == 0

def DFS(y, x):
    global cnt

    # 방문 체크
    visited[y][x] = 1

    for i in range(4):
        new_y = y + dy[i]
        new_x = x + dx[i]

        # 안전지역 체크
        if is_safe(new_y, new_x):
            # 기준이 흰색이고 다음 칸이 흰색이면 다음 칸을 검은색으로 변경(cnt + 1)
            if board[y][x] == 'W':
                if board[new_y][new_x] == 'W':
                    cnt += 1
                    board[new_y][new_x] = 'B'
            # 기준이 검은색이고 다음 칸이 검은색이면 다음 칸을 흰색으로 변경(cnt + 1)
            else:
                if board[new_y][new_x] == 'B':
                    cnt += 1
                    board[new_y][new_x] = 'W'

            DFS(new_y, new_x)

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


N, M = map(int, input().split())
origianl_board = [list(map(str, input())) for _ in range(N)]
min_cnt = 0xffffff

# 원본에서 8X8로 체스판을 만들어서 전체 탐색
for i in range(0, N-7):
    for j in range(0, M-7):
        board = [origianl_board[k][j:M+1] for k in range(i, N)]
        visited = [[0]*8 for _ in range(8)]

        # cnt 초기화
        cnt = 0

        # 생성한 체스판으로 DFS
        for row in range(0, 8):
            for col in range(0, 8):
                DFS(row, col)

        # DFS 결과로 더 적은 변경 횟수를 찾았다면 min_cnt 갱신
        if cnt < min_cnt:
            min_cnt = cnt

print(min_cnt)

imn00133 3년 전 3

좀 더 간단한 예시를 드리겠습니다.

8 8
WWWWWWWW
WWWWWWWW
WWWWWWWW
WWWWWWWW
WWWWWWWW
WWWWWWWW
WWWWWWWW
WWWWWWWB

답: 31

맨 처음이 W라고 그 다음을 B로 바꾸는게 꼭 최소값이 아닐 수 있습니다.

park3three 3년 전 0

아하 감사합니다. 간단한 수정 정도가 아니라 로직 자체가 접근에 문제가 있었네요.

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

문제

문제

출처

ICPC

DFS - 반례까지 알겠는데 어느 부분이 문제인지 모르겠습니다.

park3three 3년 전 0

imn00133 3년 전 3

park3three 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말