글 읽기 - 시간초과문제... 접근법이 잘못되었나요?

안녕하세요 문제를 푸는데 일반적으로 생각하는 백트레킹으로 해봤는데

ㅜ 모양이나 + 모양이 들어간 것을 검색하지 못해서.

현재간 좌표에서마다 백트레킹을 하나하나 보았습니다.

예를들어

X00X

0은 현재 제가 방문한 좌표입니다.

X좌표는 현재 내가 다음에 갈수있는 범위입니다.

이런식으로 백트레킹을하면 답이 나오겠다 싶어서 해보았습니다.

답은 물론 나옵니다.. 그러나 속도 이슈가 너무 큽니다..

이럴떈 어떻게 해결하면 좋을까요..

1~25 개의 숫자중에 7개를 뽑고, 이 7개의 수가 상하좌우 연결되어있는지 검사하고, 조건에 만족하는지 확인하는건 오래걸릴까요..?

이제 봤네요 제 생각은 검사하는데 있어서 n^3이라는 시간이 소요되서 그런데 저걸 줄이면 될거같습니다.

그런데 아이디어가 안떠오른다는게 함정이네요..

n^3의 검사식보다 dfs 탐색 도중에 발생하는 경우의 수가 너무 많은 것 같습니다.

for문 7개면 되지 않을까요?

댓글을 작성하려면 로그인해야 합니다.

Baekjoon Online Judge