잘 못 짠 코드 구조 정리
처음에 정확하게 로직화가 되어 있지 않은 상태에서 진행한 결과 지속적으로 프로그램이 누더기가 되어가고 있었다.
8가지 움직임 중에서 단순한 4가지만 구현한 뒤 디버깅을 시작한 일은 잘 한 것이다.
주석처리는 소괄호()로 표기한다.
총평 : parameter가 코드 작성 과정에서 자꾸 늘어나고 이것은 함수의 추적 가능성을 지나치게 나쁘게 만들었다. 그것은 정확한 로직을 끝까지 완성하지 않고 작성을 시작했기 때문이었다.
- 상하좌우, Ctrl상하좌우 8가지 방향으로 탐색을 한다는 것을 로직의 기본 아이디어로 삼았다.
- 모든 카드에 대해서 열려있다는 사실을 알고 있다는 단서가 있기 때문에 먼저 열려 있는 카드의 종류를 cnt 하는 것으로 맞춰야 할 가지수를 찾았다.
- DFS로 방향을 잡았는데 그 이유는 종료 조건을 찾았을 때 프로그램을 종료시키고 싶었기 때문이다. 종료 조건은 모든 카드 종류를 맞추고 난 뒤 cnt==0이 되었을 때를 의도했다. (DFS가 더 관리하기 힘들어졌다. 왜냐면 board를 전역변수로 사용해서 가장 먼저 진행한 DFS가 board의 카드를 모두 지워버렸기 때문이다. 원복을 처리해주어야 했을지 모른다.)
- visited 배열을 필요로 했는데, 그 이유는 DFS 탐색 과정에서 상하좌우를 할 때 이전 콜스택에서 진행했던 이동을 되돌리면 안되기 때문이었다.
(이 것이 결국 문제가 되었을 수 있다.)
-
mn: 전역변수로 선언. 최소 행동을 cnt해야하기 때문에 전역변수로 설정해두었다. 초기 값 = 1억
-
check 함수 : unique한 카드 쌍의 개수를 return 하므로 문제는 없다.
-
visited 배열: 전역변수로 사용할 예정이고 list 이므로 global 선언하지 않았음.
-
dfs 함수
파라미터(r,c,n,cnt,target,mode)
n은 check 함수에서 나온 return 값을 사용.
cnt 는 매 행동을 기록한다. +=1로 기록해주었다.
target : target은 처음 숫자(카드)를 만났을 때 기록할 용도로 만들었다. target에 해당하는 카드를 찾아내면 target은 사라져야 한다고 가정했다. target 의 값은 리스트로써[r,c]를 담고 있는데 이 두 값을 이용해서 카드 번호도 같이 표현할 수 있다.board[r][c] -
mode: mode는 불리언 값으로 target을 가지게 된 이후로 True로 변경되는 값이다. 카드 짝인 target을 찾아내면 다시 False로 바뀌어야 한다. 이 값을 넣은 이유는 mode인 경우에만 두 번째 pair 여부를 확인할 수 있기 때문이었다.
- 함수 진행
-- visited 처리 (함수가 콜 될 때마다 visited처리를 해주었다.)
-- 첫번째 분기 (board에 값이 존재할 때):
--- 하위 분기 : mode가 True이고 target으로 하는 카드 값과 현재의 카드 값이 동일한 경우 (정확히는 target과 현재의 값의 위치는 달라야 하지만 표현하지 않음)
pair를 찾았으므로 n을 1만큼 차감한다.
두 카드 pair위치를 모두 0으로 변경시켜준다.
visited를 초기화한다.
target으로 들고 있던 값을 현재 위치로 초기화 해준다. (필요한가?)
--- 아닌 경우
처음 숫자가 등장했다면 target이기 때문에 target으로 값을 넣어준다.
첫번째 분기에 따라서 mode를 뒤집어준다. (그런데 카드짝이 다른 경우인데도 mode가 변경되버리는 건 아닌가하는게 지금 보임)
카드를 열어야 하는 action이 필요하므로 cnt를 +=1 해준다.
-- 두 번째 분기: n ==0
프로그램 종료 조건이다. 가장 먼저 작성했다. 이 조건에 도달 한 경우 곧바로 cnt를 기록하는데, mn 값과 비교하여 가장 작은 경우에 mn을 갱신하도록 했다. (이 자체는 특별히 문제가 없다)
-- body: 상하좌우 이동을 수행하고 4 방향으로 dfs를 각각 수행한다. 만약 상하좌우가 경계를 벗어나거나 상하좌우가 visited 처리가 되었다면 수행하지 않는다. visited는 전역변수이므로 dfs 처리시에 원복을 하지 않으면 문제가 될 것이다. 작성된 코드에서는 dfs 원복을 전체 원복으로 처리하는 식으로 해두었는데 전체원복을 한다면 문제가 될 것이다.
import sys
sys.setrecursionlimit(10000)
def solution(board, r, c):
global mn
global recursion
mn = 100000000
recursion = 0
def check(board) -> int:
"""
unique한 카드 짝 개수를 기록한다. dfs의 종료조건에 사용한다.
:return: 카드짝의 unique한 경우의 수
"""
u_pair = set()
for j in range(4):
for i in range(4):
if board[j][i] > 0:
u_pair.add(board[j][i])
return len(u_pair)
v = [[0]*4 for _ in range(4)] # 초기 값.
def dfs(r,c,n,cnt,target:tuple,mode)->int:
print("target is: ", target)
global mn
global recursion
"""
움직임의 종료는 모두 8가지 상하좌우,ctrl 상하좌우이며 dfs로 같은 숫자를 만나면 작동횟수를 기록한다.
모든 카드 짝을 다 없애면 종료한다.
"""
v[r][c] = 1
recursion+=1
if board[r][c] > 0:
#print(f"Program opened the card at ({r}),({c})")
if mode and board[target[0]][target[1]] == board[r][c] and target[0]!=r and target[1]!=c:
print(f"target eliminated at ({r}),({c})")
print(f"target was : {target[0]},{target[1]}" )
n -= 1 # True 인 상태에서 pair를 찾았다면 n을 감소시킨다.
board[target[0]][target[1]] = 0 # target을 복원한다.
board[r][c]=0 # 두 번째 board 값을 0으로 복원한다.
board[target[0]][target[1]] = 0 # 첫 번째 board 값도 0으로 변경
for j in range(4): # visit 행렬 복원시키기.
for i in range(4):
v[j][i]=0
target = [r,c] #target 복원
print("initiated")
print("n:",n)
print("recursion: ",recursion)
else:
target = [r,c] # 숫자를 만나면 target을 설정한다.
mode = not mode
cnt += 1 # enter를 해야하기 때문에 올려준다.
# print(f"this time target is: ", target)
# print(f"counting:", cnt)
# print(f"pair to left ", n)
if n == 0:# 모든 카드를 다 뒤집었다면 종료한다.
print("program terminated!!")
for b in board:
print(b)
mn = min(cnt,mn) # 전역 변수로 처리한다.
return
# 8가지 이동이 있음.
dc = [1,-1,0,0]
dr = [0,0,-1,1]
# 상하좌우는 단순하다.
for i in range(4):
nc = c + dc[i]
nr = r + dr[i]
if nr < 0 or nr >=4 or nc < 0 or nc >=4 or v[nr][nc]:
# print(f"nr,nc: {nr},{nc}")
continue
dfs(nr, nc, n, cnt+1, target, mode)
for j in range(4): # visit 행렬 복원시키기.
for i in range(4):
v[j][i] = 0
# dfs(r,c+1) # 좌
# dfs(r,c-1) # 우
# dfs(r-1, c) # 상
# dfs(r+1, c) # 하
# control 연산
# dfs()
# dfs()
# dfs()
# dfs()
return # 정상적이라면 n이 0이 되면서 종료되므로 필요 없다. 비정상인 경우 for 문 다 돌았을 때 종료 (debug용)
n = check(board)
dfs(r,c,n,0,[r,c],False)
return mn
print(solution([[1,0,0,3],[2,0,0,0],[0,0,0,2],[3,0,1,0]],1,3))좋은 코드 분석
위 코드를 분석한다
원글 작성자는 BFS를 선택하였다. 완탐을 하는 것은 같다. 8가지 이동을 선택한 것도 같다. visit을 사용하는 것도 역시 필요하다.
저자가 중요하게 생각하는 상태는 다음과 같다.
격자의 상태 (격자의 상태라 함은 board 자체를 의미하는것인가?)
커서의 위치
현재 카드를 0 or 1장 뒤집었는지
카드를 뒤집었다면 뒤집은 카드의 위치
3번이 True면 뒤집은 카드의 위치
3번이 False면 (-1,-1)
visit을 기록하는데 2-d list가 아니라 1-d로 직렬화했다. 메모리 문제를 염려했다고 한다. (dfs라면 문제가 될지 모르겠는데 bfs에서 필요한가?)
기록하는 항목이 많기 때문에 다차원이 된다. (이것은 경주로 건설과 같은 아이디어이다. 결국 넣어주는 데이터가 5차원 혹은 6차원이다)
visit.add([초기격자상태, 커서위치, 카드 뒤집기 여부, 뒤집은 카드 위치])
q.add([초기 격자상태, 커서위치, 카드 뒤집기 여부, 뒤집은 카드 위치, 조작 횟수])
이 것들을 데이터로써 관리한다는 뜻이다.
그리고 나서 BFS를 진행하는데 아래 분기가 필요하다.
if 현재 카드를 뒤집은 상태라면
if 지금 위치의 카드와 이전에 뒤집은 카드가 같다면
격자에서 카드를 제거함
if 지금 모든 카드를 제거 했다면
return 횟수+1
else 아직 끝낼 수 없다면
바뀐 격자의 상태, 커서위치, 뒤집지 않음을 방문으로 표시
바뀐 격자의 상태, 커서위치, 뒤집지 않음을 다음에 탐색
else 짝 맞추기 실패
이전 상태, 커서의 위치, 뒤집지 않음을 방문으로 표시
이전 상태, 커서의 위치, 카드 뒤집음, 횟수 +1 을 다음에 탐색
else 카드를 하나도 안뒤집은 상태라면
if 이전의 상태, 카드를 뒤집음, 현재 커서의 위치를 방문한적 있다면:
continue
이전의 상태, 현재 커서의 위치, 카드를 뒤집음을 방문 표시
이전의 상태, 현재 커서의 위치, 카드를 뒤집음, 횟수 +1 을 다음에 탐색