SWEA_2819_격자판의 숫자 이어 붙이기

ByungHun Kim·2021년 4월 16일
0

아이디어 1

  • 반복문을 이용해, 모든 칸을 순회한다.

  • 4 방향으로 이동한다.

  • 6번째 이동인지 확인한다. (거쳐온 칸이 7칸인지 확인한다.)

    • 이동경로를 저장한다.

      저장 시, set을 활용한다. (서로 다른 일곱 자리 수들의 개수를 알아야 하는 문제이기 때문)

  • 인덱스가 벗어나지 않는지 확인한다.

  • 다시 탐색을 진행한다.

    이동하며, 몇 번째 이동인지 / 어떤 칸을 거쳐 왔는지에 대한 기록을 한다.

dr = [0, 1, 0, -1]
dc = [1, 0, -1, 0]

def search_BOARD(r, c, count, route):
    for di in range(4):
        nr = r + dr[di]
        nc = c + dc[di]

        if 0 <= nr < 4 and 0 <= nc < 4:
            t_count = count + 1
            t_route = route + BOARD[nr][nc]
            if t_count == 6:
                number_set.add(t_route)
                continue
            else:
                search_BOARD(nr, nc, t_count, t_route)


T = int(input())

for tc in range(1, T + 1):
    # 문자열로 받아도 될 것 같다.
    BOARD = [list(input().split()) for _ in range(4)]
    # print(BOARD)

    number_set = set()
    for i in range(4):
        for j in range(4):
            search_BOARD(i, j, 0, BOARD[i][j])
    # print(number_set)
    print(f"#{tc} {len(number_set)}")

다른 멋진 분들의 코드😎

1. 재귀를 활용할 때, 어떤 인자를 넘겨줄 것인가?

# 나는 몇 칸을 거쳤는지도 저장하였는데, 이어붙인 숫자의 길이로 동일한 기능을 수행할 수 있기 때문에
# 몇 칸을 거쳤는지는 없어도 큰 상관은 없겠다.
# num의 타입은 string이다. 숫자를 덧셈 계산하는 것이 아니라 순열을 만들고자 할 때에는 문자로 만드는 게 편한 것 같다.
def solve(r, c, num):
    global num_set
    
    # 탐색 종료: 이어 붙인 숫자의 길이가 7일 때,
    if len(num) >= 7:
        # set으로 선언한 num_set에 add해주어 중복을 방지하였다.
        num_set.add(num)
        return
 
    for d in delta:
        nr = r + d[0]
        nc = c + d[1]
        # 인덱스 판단을 함수로 해주는 게 재미있다.
        if is_in(nr, nc):
            # 탐색을 더이상 하지 않을 조건은 인덱스 뿐이니,
            # 인덱스 조건을 만족하면 다음 탐색으로 넘어간다.
            solve(nr, nc, num + str(board[nr][nc]))
    return
 
def is_in(r, c):
    if r < 0 or r >= N or c < 0 or c >= N:
        return False
    return True
 
delta = [(-1, 0), (1, 0), (0, -1), (0, 1)]
T = int(input())
N = 4
for test_case in range(1, T + 1):
    # solve에서 num을 문자로 다룰 거라면, 처음에 받을 때 int로 받지 않는 것이 좋았을 것 같다.
    # [list(input().split()) for _ in range(N)]
    board = [list(map(int, input().split())) for _ in range(N)]
    # set을 선언할 때, 왜 ([])를 사용했는지는 잘 모르겠다.
    num_set = set([])
 
    for i in range(N):
        for j in range(N):
            solve(i, j, '')
 
    print('#{} {}'.format(test_case, len(num_set)))
profile
Maker가 되고 싶은 개발자

0개의 댓글