문제
4×4 크기의 격자판이 있다. 격자판의 각 격자칸에는 0부터 9 사이의 숫자가 적혀 있다.
격자판의 임의의 위치에서 시작해서, 동서남북 네 방향으로 인접한 격자로 총 여섯 번 이동하면서, 각 칸에 적혀있는 숫자를 차례대로 이어 붙이면 7자리의 수가 된다.
이동을 할 때에는 한 번 거쳤던 격자칸을 다시 거쳐도 되며, 0으로 시작하는 0102001과 같은 수를 만들 수도 있다.
단, 격자판을 벗어나는 이동은 가능하지 않다고 가정한다.
격자판이 주어졌을 때, 만들 수 있는 서로 다른 일곱 자리 수들의 개수를 구하는 프로그램을 작성하시오.
[입력]
첫 번째 줄에 테스트 케이스의 수 T가 주어진다.
각 테스트 케이스마다 4개의 줄에 걸쳐서, 각 줄마다 4개의 정수로 격자판의 정보가 주어진다.
[출력]
각 테스트 케이스마다 ‘#x ’(x는 테스트케이스 번호를 의미하며 1부터 시작한다)를 출력하고, 격자판을 이동하며 만들 수 있는 서로 다른 일곱 자리 수들의 개수를 출력한다.풀이
4x4의 격자판에서, 임의의 한점에서 시작해 상하좌우로 7번 움직여서 만들어지는 문자열의 총 개수를 구하는 문제이다.
이때, 이미 들렀던 장소를 또 들러도 되는것이 중요!
- 4x4의 각 격자를 순회한다
- 한 격자에서 출발해, 상하좌우로 1번씩 움직이며 bfs를 순회한다.
- 이때, 이동한 위치가 격자밖을 나가면 안되며, 7번 다 움직일 경우 딕셔너리에 추가
- 딕셔너리로 중복된 문자열이 없게 체크! - 최종적으로 딕셔너리의 길이를 리턴!
from collections import deque
res=[]
dx=[0,0,-1,1]
dy=[1,-1,0,0]
def bfs(count,s,x,y):
if count==7:
if s not in dic:
dic[s]=1
return
for i in range(4):
nx=x+dx[i]
ny=y+dy[i]
if 1<=nx<=4 and 1<=ny<=4:
bfs(count+1,s+str(li[nx][ny]),nx,ny)
for m in range(int(input())):
tmp=0
dic={}
li=[[0]]
for i in range(4):
li.append([0]+list(map(int,input().split())))
for i in range(1,5):
for j in range(1,5):
bfs(0,'',i,j)
tmp=len(dic)
res.append(tmp)
for i in range(len(res)):
print("#%d %s"%(i+1,res[i]))시간초과가 될 것 같았지만, 이풀이말고 크게 떠오르는게 없어서 해봤는데 다행이넹 ㅎ
뉴비