[BAEKJOON] 17070 파이프 옮기기 1

BAEKJOON] 17070 파이프 옮기기 1 - c

문제

그래프의 크기 n과 그래프를 입력받는다.

빈칸은 0, 벽은 1이며 파이프는 1*2(r, c) 형태이다.

이 문제는 일반 탐색 문제와는 달리 이동 뿐 아니라 대각선의 회전을 생각해야한다.

DFS의 백트레킹으로 python 구현을 했으나, 시간 조건 기준이 까다로워 C로 구현해 통과시켰다. bfs로 구현을 해야 시간초과를 벗어날 수 있을 것 같다.(추후에 추가할 수 있기를…)

• c

  현재 들어온 벽과 빈칸의 정보를 Map으로, 방문 여부를 visited로 체크한다.

  #include <stdio.h>
  
  int n;
  int cnt;
  int Map[20][20];
  int visited[20][20];
  
  int is_wall(int r, int c) {
  	if (r < 0 || r >= n || c < 0 || c >= n) {
  		return 1;
  	}
  	return 0;
  }
  
  void Backtracking(int hr, int hc, int tr, int tc) {
  	visited[hr][hc] = 1;
  	
    // (n, n)에 도달했을 때
  	if (hr == n - 1 && hc == n - 1) {
  		cnt++;
  	}
    
    // 모든 경우에 우측 대각선 아래로 이동 가능하다. 때문에 모든 경우에 체크.
  	if (is_wall(hr + 1, hc + 1) == 0 && visited[hr + 1][hc + 1] == 0 && Map[hr + 1][hc + 1] == 0) {
  		if (Map[hr + 1][hc] == 0 && Map[hr][hc + 1] == 0) {
  			Backtracking(hr + 1, hc + 1, hr, hc);
  		}
  	}
    
    // row가 동일할 때. 즉, 가로로 위치해 있을 때 또는 대각선으로 위치해 있을 경우
  	if (hr == tr || (hr == tr + 1 && hc == tc + 1)) {
        // 가로의 이동만을 체크한다.
  		if (is_wall(hr, hc + 1) == 0 && visited[hr][hc + 1] == 0 && Map[hr][hc + 1] == 0) {
  			Backtracking(hr, hc + 1, hr, hc);
  		}
  	}
    
    // col이 동일할 때. 즉, 세로로 위치해 있을 때 또는 대각선으로 위치해 있을 경우
  	if (hc == tc || (hr == tr + 1 && hc == tc + 1)) {
        // 세로의 이동만을 체크한다.
  		if (is_wall(hr + 1, hc) == 0 && visited[hr + 1][hc] == 0 && Map[hr + 1][hc] == 0) {
  			Backtracking(hr + 1, hc, hr, hc);
  		}
  	}
  
  	visited[hr][hc] = 0;
  }
  
  int main(void) {
  	scanf("%d", &n);
  	for (int r = 0; r < n; r++) {
  		for (int c = 0; c < n; c++) {
  			scanf("%d ", &Map[r][c]);
  		}
  	}
  	for (int r = 0; r < n; r++) {
  		for (int c = 0; c < n; c++) {
  			visited[r][c] = 0;
  		}
  	}
  
  	cnt = 0;
  	Backtracking(0, 1, 0, 0);
  	printf("%d", cnt);
  	return 0;
  }

  
  
  
  

• python - 시간초과

  아래의 코드는 시간초과가 난 backtracking 코드이다.

  def is_wall(r, c):
    if r<0 or r>= n or c < 0 or c>= n:
        return True
    return False
  
  
  def backtracking(hr, hc, tr, tc):
    global cnt
    visit[hr][hc] = 1
    # print(hr, hc, tr, tc)
    # for i in range(n):
    #     print(visit[i])
    # print()
    if hr == n-1 and hc == n-1:
        cnt += 1
    # all
    if not is_wall(hr+1, hc+1) and not visit[hr+1][hc+1]:
        if not Map[hr+1][hc+1] and not Map[hr+1][hc] and not Map[hr][hc+1]:
            backtracking(hr+1, hc+1, hr, hc)
    # 가로
    if hr == tr or (hr == tr + 1 and hc == tc + 1):
        if not is_wall(hr, hc+1) and not visit[hr][hc+1]:
            if not Map[hr][hc+1]:
                backtracking(hr, hc+1, hr, hc)
    # 세로
    if hc == tc or (hr == tr + 1 and hc == tc + 1):
        if not is_wall(hr+1, hc) and not visit[hr+1][hc]:
            if not Map[hr+1][hc]:
                backtracking(hr+1, hc, hr, hc)
  
  
    visit[hr][hc] = 0
  
  
  n = int(input())
  Map = []
  
  for i in range(n):
    Map.append(list(map(int, input().split())))
  
  visit = [[0 for _ in range(n)] for _ in range(n)]
  cnt = 0
  
  backtracking(0, 1, 0, 0)
  
  
  
  print(cnt)