SWEA 2819. 격자판의 숫자 이어 붙이기 (Python, DFS, 완전탐색, D4)

SWEA 2819. 격자판의 숫자 이어 붙이기 문제 바로가기

문제 접근

4by4의 격자판에서 임의의 위치에서 시작해 상하좌우로 움직이며 격자판의 숫자들을 이어붙이고, 그 서로 다른 이어붙인 숫자들의 개수를 구하면 되는 문제이다.
따라서 숫자들을 이어붙이기 편리한 DFS를 사용하여 구현할 수 있겠다고 생각했다. 또한 4x4로 격자판이 되게 작기 때문에 시간내에 충분히 풀 수 있다고 생각해서 완전탐색을 바로 시도했다.

문제 풀이

DFS

파라미터로 x,y,result를 받는다. result에는 이전까지 이어붙인 수가 들어있다. 따라서 dfs가 실행될 때 pan에 x,y좌표에 있는 숫자를 result에 이어붙이고 만약 result가 7자리가 됐다면 answer이라는 결과를 저장하는 리스트에 추가한다. 만약 7자리가 안됐다면 좌표를 상하좌우로 바꾸어 다시 실행한다.

def dfs(x,y, result):
        if x<0 or y<0 or x>=4 or y>=4:
            return
        result+=pan[x][y]
        if len(result)==7:
            answer.append(result)
            return
        dfs(x+1,y,result) # 하
        dfs(x,y+1,result) # 우
        dfs(x-1,y,result) # 상
        dfs(x,y-1,result) # 좌

DFS 실행코드

임의의 위치에서 시작한다고 했기 때문에 모든 곳에서 시작할 수 있다. 따라서 모든 위치에서 dfs를 실행해본다.

for i in range(4):
	for j in range(4):
    	dfs(i,j,'')

중복 제거

중복 제거는 파이썬의 set이라는 집합자료형을 사용했다. 이 경우 리스트에서 중복인 수들은 하나만 남기 때문에 편리하게 중복을 제거할 수 있다.

print(f'#{test_case} {len(set(answer))}')

제출 코드

T = int(input())
for test_case in range(1, T + 1):
    pan = []
    for i in range(4):
        line = list(map(str, input().strip().split()))
        pan.append(line)
    answer = []
    def dfs(x,y, result):
        if x<0 or y<0 or x>=4 or y>=4:
            return
        result+=pan[x][y]
        if len(result)==7:
            answer.append(result)
            return
        dfs(x+1,y,result) # 하
        dfs(x,y+1,result) # 우
        dfs(x-1,y,result) # 상
        dfs(x,y-1,result) # 좌
    for i in range(4):
        for j in range(4):
            dfs(i,j,'')
    print(f'#{test_case} {len(set(answer))}')