백준 구현 대비 테트로미노

문제:https://www.acmicpc.net/problem/14500

접근

1.테트로미노가 가질 수 있는 경우의 수를 move 리스트 변수안에 선언 (23개)
2. bruteforce, 그래프의 각 위치를 순회하며 move 변수 또한 순회(23x4xNxM===대략 최대 25000000 가능)

move=[
  [[0,0],[0,1],[0,2],[0,3]],
  [[0,0],[1,0],[2,0],[3,0]],
  [[0,0],[0,1],[1,0],[1,1]],
  [[0,0],[1,0],[2,0],[2,1]],
  [[0,0],[1,0],[2,0],[0,1]],
  [[0,0],[1,0],[2,0],[0,-1]],
  [[0,0],[1,0],[2,0],[2,-1]],
  [[0,0],[1,0],[1,-1],[1,-2]],
  [[0,0],[1,0],[1,1],[1,2]],
  [[0,0],[1,0],[0,-1],[0,-2]],
  [[0,0],[1,0],[0,1],[0,2]],
  [[0,0],[1,0],[1,1],[2,1]],
  [[0,0],[0,1],[-1,1],[-1,2]],
  [[0,0],[1,0],[1,-1],[2,-1]],
  [[0,0],[0,1],[1,1],[1,2]],
  [[0,0],[0,1],[0,2],[1,1]],
  [[0,0],[0,1],[0,2],[-1,1]],
  [[0,0],[1,0],[2,0],[1,1]],
  [[0,0],[1,0],[2,0],[1,-1]]
]
N,M=map(int, input().split())
graph=[]
maxanswer=0
for i in range(N):
  graph.append(list(map(int, input().split())))
for i in range(N):
  for j in range(M):
    for mo in move:
      answer=0
      for m in mo:
        ni,nj=i+m[0],j+m[1]
        if 0<=ni<N and 0<=nj<M:
          answer+=graph[ni][nj]
        else:
          break
      maxanswer=max(maxanswer,answer)
print(maxanswer)

다른 접근

각 테트로미노는 ㅗ 모양을 제외하면 길이가 4인 dfs

이를 도식화 하면 다음과 같다.
1. 크기가 4개짜리 테트로미노 dfs
2. 크기가 3개짜리 검사 (ㅗ ㅜ ㅏ ㅓ 같은애들)

주의할점
1.일반적인 dfs는 한번 탐색한 곳을 다시 탐색하지 않는다. 그러나 이 경우에는 한번 방문이 끝나면 다시 미방문 처리를 해주어야함. 즉 모든 경우의 수를 탐색해주어야 함 이를 백트래킹이라고 부름
2. bfs가 안되는 이유는 되돌아올수 없기 때문

코드

for(int i=0; i<4; i++){
    int nx = x + dx[i];
    int ny = y + dy[i];

    // 지도 넘어가는 경우 검사
    if(nx < 1 || nx > n || ny < 1 || ny > m) continue;

    // 방문하지 않은 점이면
    if(!check[nx][ny]) {

        // 들어가기전 체크해주고
        check[nx][ny] = true;

        dfs(nx, ny, sum_value + a[nx][ny], length + 1);
        // 하나의 탐색을 완료하면 여기로 돌아옵니다.

        // 나올때 체크를 해제합니다.
        check[nx][ny] = false;
    }
}