[SWEA][D4] 2819. 격자판의 숫자 이어 붙이기 DFS 파이썬

📌 문제출처 https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV7I5fgqEogDFAXB

 📖[D4] 2819. 격자판의 숫자 이어 붙이기 

[문제]

 

4×4 크기의 격자판이 있다. 격자판의 각 격자칸에는 0부터 9 사이의 숫자가 적혀 있다.

격자판의 임의의 위치에서 시작해서, 동서남북 네 방향으로 인접한 격자로 총 여섯 번 이동하면서, 각 칸에 적혀있는 숫자를 차례대로 이어 붙이면 7자리의 수가 된다.

이동을 할 때에는 한 번 거쳤던 격자칸을 다시 거쳐도 되며, 0으로 시작하는 0102001과 같은 수를 만들 수도 있다.

단, 격자판을 벗어나는 이동은 가능하지 않다고 가정한다.
격자판이 주어졌을 때, 만들 수 있는 서로 다른 일곱 자리 수들의 개수를 구하는 프로그램을 작성하시오.

[입력]

첫 번째 줄에 테스트 케이스의 수 T가 주어진다.
각 테스트 케이스마다 4개의 줄에 걸쳐서, 각 줄마다 4개의 정수로 격자판의 정보가 주어진다.

1
1 1 1 1
1 1 1 2
1 1 2 1
1 1 1 1

[출력]

각 테스트 케이스마다 ‘#x ’(x는 테스트케이스 번호를 의미하며 1부터 시작한다)를 출력하고, 격자판을 이동하며 만들 수 있는 서로 다른 일곱 자리 수들의 개수를 출력한다.

#1 23

...

---

💡  [D4] 2819. 격자판의 숫자 이어 붙이기 - DFS 재귀 파이썬 풀이

 

문제를 읽어보니 지금까지 접한 D4 중 에서는 제일 해 볼 만 했다. 다행다행!

크기도 4x4 로 고정되어있고, 이동 할 때 갔던 곳 다시 갈 수도 있다고 하니!

그동안 배웠던 거 아무것도 보지 않고 짜보기로 했다. 디버깅도 해보면서 문제를 하나씩 해결해보자!

 

지난 간 길을 체크하거나 제외하거나 신경쓰지 않아서 ㅠㅠ

하지만, 다른 문제를 위해 갔던 곳을 갈 수 없다는 상황도 할 줄 알아야 겠지...    

 

<구조>

 

1.  주어진 영역 내에서만 이동이니, 상하좌우 봐서 갈 수 있으면 가면 못 갈 것 같으면 안가고 체크.

    주의 ::  y,x 가 영역 밖인데 arr[y][x] 하면 idex out of range 바로 뜬다. 

 

2.  일곱자리 수를 어쨌든 만들면, 서로 다른 구성만 1개로 인정하니깐

    딕셔너리는 중복된 키를 허용하지 않는 특성이 생각나서,  딕셔너리 키로 해버려야지. 했다.

    키의 해당 값은 아무거나 생관없을 것이고( 몇번 나왔는지 카운트 할 것도 아니고..)

 

3. 일곱자리 수는 = 이전값*10+현재격자판숫자 ... 하는 것보다 str으로 하나씩 뒤로 연결하는게 편해서

   ''+'' 했다. 재귀를 나올때, 쓴 걸 지울때 ''-'' 가 먹지 않으니깐 [:-1] 뒤를 하나 슬라이스 했다.  

    

 

💡 <코드 PASS>

# [D4] 2819. 격자판의 숫자 이어 붙이기 - DFS 재귀 파이썬 풀이
# 풀이 : 2020.03.05 경칩
# 시간 : 1시간 구성 연습 + 1시간 작성 및 디버깅 및 요약
 
#이동 우하좌상 
dy = [0,1,0,-1]
dx = [1,0,-1,0]
def move(makenum,y,x):
    global seven_dic,seven_ret
    # 바닥 케이스
    if len(makenum) == 7:
        seven_dic[makenum] = 'Cindy' # 키 : 값은아무거나
        return
    # 재귀 케이스
    for i in range(4): # 우하좌상 주변 살펴보기
        next_y = y + dy[i]
        next_x = x + dx[i]
        if 0<=next_y<4 and 0<=next_x<4: # 벽 아니면 거기로 이동 가
            makenum += arr[next_y][next_x] # 추가
            move(makenum,next_y,next_x) # 재귀재귀
            makenum = makenum[:-1] # 빼기      
 
for t in range(1,int(input())+1):
    seven_dic = {} # 케이스 돌 때마다 초기화
    arr = [list(input().split()) for _ in range(4)] # 2차원배열
    for y in range(4):
        for x in range(4):
            makenum = arr[y][x] # 시작 
            move(makenum,y,x) # 나머지이동
    print(f'#{t} {len(seven_dic)}') # 딕셔너리 내 키의 개수 => 서로 다른 7가지 조합
 
 

 

print(seven_dic) {'1111211': 'Cindy', '1111212': 'Cindy', '1111112': 'Cindy', '1111111': 'Cindy', '1112111': 'Cindy', '1112121': 'Cindy', '1111121': 'Cindy', '1121111': 'Cindy', '1121112': 'Cindy', '1121211': 'Cindy', '1121212': 'Cindy', '1211111': 'Cindy', '1211121': 'Cindy', '1212111': 'Cindy', '1212121': 'Cindy', '2111111': 'Cindy', '2111112': 'Cindy', '2111211': 'Cindy', '2111212': 'Cindy', '2121111': 'Cindy', '2121112': 'Cindy', '2121211': 'Cindy', '2121212': 'Cindy'}

 

 

<상세설명 및 풀이> 의식의 흐름대로 작성했던 초기 ..

# [D4] 2819. 격자판의 숫자 이어 붙이기 - DFS 재귀 파이썬 풀이
# 연습 연습 - 상 세 설 명
 
# 우 하 좌 상
dy = [0,1,0,-1]
dx = [1,0,-1,0]
def iswell(y,x): # 가로 세로 이동 하려고 할 때 
    if x<0 or x>=len(arr[0]) or y<0 or y>=len(arr):
        return True # 벽임 못감
    return False # 벽아님 감
 
def move(makenum,y,x,arr):
    global seven_dic,seven_ret
    # 바닥 케이스
    if len(makenum) == 7:
        if  makenum not in seven_dic: # 키가 딕에 없으면
            seven_dic[makenum] = 1 # 키 : 값은아무거나
            seven_ret = seven_ret + 1 # 새 조합이구나! 카운트 
        return
    # 재귀 케이스
    for i in range(4): # 상하좌우 네방향 보기
        next_y = y + dy[i]
        next_x = x + dx[i]
        if not iswell(next_y,next_x): # 벽 아니면 거기로 가
            makenum += arr[next_y][next_x]
            move(makenum,next_y,next_x,arr)
            makenum = makenum[:-1]
        # 벽이면 다른 영역살펴보기        
 
def solution(arr):
    for y in range(len(arr)):
        for x in range(len(arr[0])):
            makenum =''
            makenum += arr[y][x] # 시작
            move(makenum,y,x,arr)
    return
    
T = int(input())
for t in range(1,T+1):
    seven_dic = {} # 있다없다보기가 빠름.''없으면 키로 넣어주기,및 키 존재만 카운트세기
    seven_ret = 0
    # 4바이4격자판 2차원 배열로 받기
    arr = [list(input().split()) for _ in range(4)] # arr[0][0]~ arr[3][3]
    solution(arr)
    print(f'#{t} {seven_ret}')
 
 

 

 

👀 <시행착오>

 

풀어가는 과정에서 디버깅해서 문법적 오류나 실수들을 잡아가며, 어찌어찌 결과 값이 나오긴 했는데 , 테스트 케이스랑 달라서 문제푼 사람들에게 물어보며 고민..., dic 의 결과값을 보다가 이상한 조합을 발견, 22가 연속해서 나올수 없는데!!! 알고보니 상하좌우 중 하나를 대각선방향으로 넣은 것!!! 테스트케이스 모양이 잘 나와있어서 파악했지 눈물.

 

그리고 SET함수!

리스트를 다 만들고 마지막에 set으로 흔들어서 중복을 없애서 len(result_list) 해서 출력할 수 있겠지만, 

처음에 result_list 선언시 set() 을 써서 하면, 추후 result_list 에 append 시킬 때 자동으로 걸러지는!!! 오오!!!

써 본 적이 없었는데 좋은 걸 하나 배웠다. 순열 중복 거를 때 좋겠다. 얼른 이용해봐야지