visited[nx][ny] = 0 의 유무에 따른 값의 차이 ?? 백준16929번

Question

https://www.acmicpc.net/problem/16929# 사이클이 존재하는지 확인하는 함수 def cycle(color, x, y, cnt, start_x, start_y): global ans # 이미 사이클을 찾았다면 종료 if ans is True: return # 4가지 방향에 대하여 for i in range(4): # 이동 위치 좌표 설정 nx, ny = x + dx[i], y + dy[i] # 이동 위치가 게임판을 벗어나면 건너뛰기 if nx < 0 or nx >= n or ny < 0 or ny >= m: continue # 사이클이 존재(4개 이상 점 연결, 처음 시작지점 도달)한다면 if cnt >= 4 and nx == start_x and ny == start_y: # 정답 존재 표시 ans = True return # 색깔이 같고 아직 방문하지 않았다면 if board[nx][ny] == color and visited[nx][ny] == 0: # 방문 표시 visited[nx][ny] = 1 # 재귀적으로 수행 cycle(color, nx, ny, cnt + 1, start_x, start_y) # 방문 표시 해제 visited[nx][ny] = 0 # 게임 시작 함수 def game_start(): for i in range(n): for j in range(m): # 사이클 시작 위치 좌표 start_x, start_y = i, j # 방문 표시 visited[start_x][start_y] = 1 # 사이클이 존재하는지 함수 실시 cycle(board[i][j], i, j, 1, start_x, start_y) # 사이클이 존재한다면 if ans: return 'Yes' # 사이클이 존재하지 않는다면 return 'No' n, m = map(int, input().split()) board = [[a for a in input().rstrip()] for _ in range(n)] # 방문 visited = [[0] * m for _ in range(n)] # 동, 남, 서, 북 방향 표시 dx = [0, 1, 0, -1] dy = [1, 0, -1, 0] # 정답 변수 ans = False # 정답 출력 print(game_start())깔끔하게정리 def cycle(color, x, y, cnt, start_x, start_y): global ans if ans is True: return for i in range(4): nx, ny = x + dx[i], y + dy[i] if not (0<=nx= 4 and nx == start_x and ny == start_y: ans = True return if board[nx][ny] == color and visited[nx][ny] == 0: visited[nx][ny] = 1 cycle(color, nx, ny, cnt + 1, start_x, start_y) # visited[nx][ny] = 0 # 게임 시작 함수 def game_start(): for i in range(n): for j in range(m): start_x, start_y = i, j visited[start_x][start_y] = 1 cycle(board[i][j], i, j, 1, start_x, start_y) if ans: return 'Yes' return 'No' n, m = map(int, input().split()) board = [[a for a in input().rstrip()] for _ in range(n)] visited = [[0] * m for _ in range(n)] dx = [0, 1, 0, -1] dy = [1, 0, -1, 0] ans = False print(game_start())def cycle에 보면 방문표시를 해제하는 이런코드가 있습니다.visited[nx][ny] = 0 이 코드의 유무에 따라예제3번의 답이 달라집니다. 예제4번4 4 YYYR BYBY BBBY BBBY원래는 답이 YES인데visited[nx][ny] = 0 이코드를 없애면NO가 나오더라구요. 근데 이 코드를 처음 접해봐서 이해가 잘안됩니다.문제가 어려워서 해설을 보고 풀었는데, 이코드가 왜 필요한지 이해가 안됩니다ㅠ예제3번은 visited[nx][ny] = 0이 코드의 유무로 정답이 달라지지만,예제1번은 그렇지않습니다. 이 코드를 없애도 답은 동일하게 yes가 나옵니다3 4 AAAA ABCA AAAA예제1번에선,visited[nx][ny] = 0 이 코드 없이 예제1번을 풀면, 답이 올바르게 나오는데,반례(에졔3번)가 존재하니, 반드시 필요한 코드인듯합니다.3 4 AAAA ABCA AAAAvisited[nx][ny] = 0 이 코드없이이 문제를 풀면BOARD는111110011111이렇게 나옵니다.반대로, 올바르게해설대로 풀면(visited[nx][ny] = 0 코드포함)111110011111을 만들었다가000000000000으로 BOARD를 만들고 끝냅니다.근데, 그냥111110011111이렇게 냅두면 안되나요?왜굳이000000000000으로 만들어야 하나요?

다크 템플러 · Accepted Answer

뭔가 시스템을 잘못 알고 계신 것 같습니다.기본적으로 코딩 테스트 문제는 문제에서 제시하는 조건을 무조건 만족해야 합니다.예시 1번을 만족했으니 예시 3번을 만족하지 않아도 되는 게 아닙니다.보아하니 정답 코드는 모든 점에 대해서 DFS를 수행하는 것으로 보입니다.1번의 경우, 0,0에서 출발해서 바로 정답 사이클로 이어집니다.하지만 3번의 경우 0,1에서 일단 첫 번째로 사이클 검사를 합니다.이 과정에서 0,2를 거치게 되는데, 0,2는 정답 사이클에 포함되어야 합니다.YYYRBYBYBBBYBBBY강조표시한 저 6개의 B가 답변이 될 것 같은데,만약 사이클을 빠져나오면서 0으로 다시 바꿔주지 않으면0,1에서 사이클이 출발할 때 0,2가 이미 방문한 것으로 취급되어0,2을 포함하는 사이클을 답으로 찾을 수 없게 됩니다.3번 예시 입력값을 따라가면서 왜 틀렸는지를 파악해보세요.3번이 틀린 순간 1번이 맞아도 그 코드는 답변이 될 수가 없습니다.

visited[nx][ny] = 0 의 유무에 따른 값의 차이 ?? 백준16929번

1개의 답변

Q&A 목록