[SWEA]2819_격자판의 숫자 이어붙이기

정답은 하단에

• 처음 접근 방법(오답)
  처음에는 BFS로 접근했다. 아직 DFS와 BFS의 개념과 사용쓰임에 대해 잘 이해하지 못했기 때문이다.

from collections import deque

def BFS(si, sj):
    global str_                                         # 전역변수
    global lst                                          # 전역변수
    q = deque([])                                       # 덱 사용
    q.append([si, sj])                                  # 초깃값 입력(원점에서 시작한다.), (0,0)

    while q:                                            # 덱 안에 좌표가 없을 때 까지 반복한다.
        ci, cj= q.popleft()                             # 덱에 들어있는 가장 왼쪽 좌표값을 꺼낸다.
        str_ = arr[ci][cj]                              # 7자리의 숫자의 초깃값으로 현재 위치를 설정한다.
        if (ci==3) and (cj==3):                         # 마지막 좌표까지 도달할 경우 종료한다.
            return lst                                  # 7자리의 숫자가 담긴 리스트를 반환한다.
        for di, dj in ([-1,0], [1,0], [0,-1], [0, 1]):  # 동서남북 네 방향으로 이동한다. ★ 여섯번 이동이 고려되지 않았다.
            ni, nj = ci + di, cj + dj                   # 이동한 좌표 값
            if 0<=ni<4 and 0<=nj<4:                     # 좌표가 범위 내에 있는지 확인한다.
                str_ += arr[ni][nj]                     # 범위 내에 있을 경우 해당 좌표값을 문자열에 더해준다.
                q.append([ni,nj])                       # 나중에 해당 좌표로 이동할 수 있도록 이동한 좌표 값을 덱에 더해준다.
        lst += [str_]                                   # 여섯번의 이동을 끝낸 후 7자리의 숫자를 리스트에 담아준다.


T = int(input())

for test_case in range(1, T+1):
    arr = [list(input().split()) for _ in range(4)]
    print(arr)
    str_ = ''                                           # 7자리의 숫자
    lst = []                                            # 7자리의 숫자가 담긴 리스트
    ans = len(lst)                                      # 7자리의 숫자가 담긴 리스트에서 set함수를 이용하여 중복을 제거한 값을 담으려고 한다.
    BFS(0,0)
    # print(lst)
    # print(f'#{test_case} {ans}')

개념부터 다시

BFS

• 한번에 한 단계씩 발전하여,
• 목적지까지 가는데 걸리는 시간, 특정 목적지까지 갈 수 있느냐의 여부, 어디가 제일 좋은 위치인가에 대한 판단이 가능하다.
• 초기에 queue나 visited를 생성한다.

DFS/백트래킹

• 가능한 모든 경우를 처리해서 답을 찾는 문제
• 시간 초과를 고려해야 한다.
• 종료 조건을 잘 체크해야 한다.
• 가능한 모든 경우를 표현하는 효율적인 방법은 Tree이다.

'격자판의 숫자 이어붙이기'또한 가능한 모든 경우를 처리해서 답을 찾는 문제이므로 DFS를 이용하여 풀어야 한다.

정답

DFS로 다시 짜서 통과할 수 있었다.

def DFS(ci, cj, str_):                              # 초기 좌표값과 일곱자리의 숫자를 담을 문자열을 전달받는다.
    global set_                                     # 7자리의 숫자들을 담을 변수. set을 통해 중복을 제거한다.

    # 종료조건
    if len(str_) == 7:                              # 일곱자리의 숫자가 완성되면 종료한다.
        set_.add(str_)                              # 이 떄, set_ 에 해당 문자열을 더해준다.
        return
    # 함수호출 (4방향 호출)
    for di, dj in ([-1,0], [1,0], [0,-1], [0, 1]):  # 상, 하, 좌, 우 방향
        ni = ci + di                                # 새로운 좌표값(행)
        nj = cj + dj                                # 새로운 좌표값(열)
        if 0<=ni<4 and 0<=nj<4:
            # str_ += arr[ni][nj]                   # ★ 1, 11 식으로 2번 누적되서 문제였던 코드
            DFS(ni, nj, str_ + arr[ni][nj])


T = int(input())

for test_case in range(1, T+1):
    arr = [list(input().split()) for _ in range(4)] # 격자판의 정보를 입력받는다.
    str_ = ''                                       # 7자리의 숫자를 담을 변수(문자열로 취급)
    set_ = set()                                    # 7자리의 숫자들을 담을 변수. set을 통해 중복을 제거한다
    cnt = 0
    for i in range(4):
        for j in range(4):
            DFS(i, j, arr[i][j])                    # DFS 함수에 원점의 좌표값과 일곱자리의 숫자를 담을 문자열을 전달한다.
    print(f'#{test_case} {len(set_)}')