[필수]백준: 컴백홈_1189

https://www.acmicpc.net/problem/1189

1189번: 컴백홈

핵심 아이디어

R x C 맵에 못가는 부분 T가 주어지고 거리 K가 주어지면 한수가 집까지도 도착하는 경우 중 거리가 K인 가짓수를 구하는 것.

• 백트래킹은 한정 조건을 가진 문제를 해결하는 전략으로, 탐색을 줄일 수 있다.
• DFS는 모든 경우를 탐색하지만, 백트래킹+DFS는 불필요한 탐색을 하지 않음.
• 백트래킹은 BFS와 DFS와 모두 구현이 가능하지만, 조건에 부합하지 않으면 이전 노드로 돌아와야하기 때문에 구조적으로 DFS구현이 편함
• 이 문제에서 백트래킹 한정조건은  graph[nx][ny] == '.' 이다. '.' 일 때 '.'을 'T'로 바꿔 방문처리를 하고 탐색을 시작한다. 탐색이 끝나면 'T'를 '.'로 돌려 놓아 다른방향으로 다시 탐색 하도록 한다.

import sys # 입력을 더 빨리 받기 위해서 sys 모듈 가져오기
input = sys.stdin.readline


r, c, k = map(int, input().split())
graph = []
for _ in range(r):
	graph.append(list(input().rstrip())) # 공백을 읽기 않기 위해 rstrip()

# 다음 노드로 이동하기 위한 방향 정의
# 상 하 좌 우
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

result = 0
def dfs(x,y,distance):
	global result
	# 목표지점 : (0, c-1)
	# 목표 거리: k
	if distance == k and y == c-1 and x == 0:
		result += 1
	else:
		# T로 방문처리
		graph[x][y] = 'T'
		# 주어진 위치에서 상 하 좌 우 살표보기
		for i in range(4):
			nx = x + dx[i]
			ny = y + dy[i]
			# 백트래킹 한정조건 : graph[nx][ny] == '.'
			if(0<= nx < r) and (0 <= ny < c) and graph[nx][ny] == '.':
				graph[nx][ny] = 'T' # 이동 가능하면 다음 위치 방문 처리
				dfs(nx,ny,distance+1) #재귀호출
				# 끝까지 탐색한 후 원래 상태로 돌려놓아 다른 방향으로 다시 탐색하도록 한다.
				graph[nx][ny]='.'

#시작점: (r-1, 0)
#초기 distance : 1
dfs(r-1,0,1)
print(result)

C++

#include <iostream>
#include <string>
using namespace std;


int n, m, k;
char graph[6][6];
int visited[6][6];

// 방향 정의
int dx[4] = { -1,1,0,0 };
int dy[4] = { 0,0,-1,1 };
int ans = 0;
void dfs(int x, int y, int distance) {
	if (x == 0 && y == m - 1 && distance == k) {
		ans++;
		return;
	}
	// 현재 위치 방문처리
	visited[x][y] = 1;
	for (int i = 0; i < 4; i++) {
		int nx = x + dx[i];
		int ny = y + dy[i];

		if (0 <= nx && nx < n  && 0 <= ny && ny < m && !visited[nx][ny] && graph[nx][ny] == '.') {
			visited[nx][ny] = 1;
			dfs(nx, ny, distance + 1);
			visited[nx][ny] = 0;
		}
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);

	// 맵의 크기 와 거리 입력받기
	cin >> n >> m >> k;
	// 맵 정보 입력 받기
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> graph[i][j];
		}

	}
	dfs(n - 1, 0, 1);
	cout << ans << '\n';
	
}

추가 학습

C++ 풀이가 익숙하지 않아 조건문와 visited 초기화 등에 헷갈리는 상황이 있어 기본적인 코드가 다음과 같이 똑같다는 것을 공부했다.

	for (int d = 0; d < 4; d++) {
		int nx = x + dx[d];
		int ny = y + dy[d];
		if (0 <= nx && nx < n && 0 <= ny && ny < m) {
			if ( !visited[nx][ny] && graph[nx][ny] == '.') {
				visited[nx][ny] = 1;
				dfs(nx, ny, distance + 1);
				visited[nx][ny] = 0;
			}
		}
	}

	for (int d = 0; d < 4; d++) {
		int nx = x + dx[d];
		int ny = y + dy[d];
		if (0 <= nx && nx < n && 0 <= ny && ny < m
			&& !visited[nx][ny] && graph[nx][ny] == '.') {
				visited[nx][ny] = 1;
				dfs(nx, ny, distance + 1);
				visited[nx][ny] = 0;
			
		}
	}