문제 URL : www.acmicpc.net/problem/9944
9944번: NxM 보드 완주하기
N×M 보드 위에서 할 수 있는 게임이 있다. 보드는 크기가 1×1인 정사각형 칸으로 나누어져 있다. 보드의 각 칸은 빈 칸 또는 장애물이다. 장애물은 아래 그림에선 어두운 사각형으로 표시되어져
www.acmicpc.net
문제 접근법 : 어떤 지점에서든 좌우상하 벽에닿을때까지 직선으로 움직였을때 모든 맵을방문할수 있는지 확인하는겁니다. 모든맵을 방문했을때 방향을 최소한 적게 바꿔서 그 바꾼횟수의 값을 구하는 문제입니다.
그것을 구하기위해서는 역시 DFS로 모든 경우의수를 탐색해야합니다.
이번문제는 상당히 많이 틀렸었는데 두가지 경우
첫번째: freopen 쓰게되면 늘 주석 처리하세요 백준에서 freopen 입력형식 파일이름이 어떻게 되있는지 모르겠지만
사용시 대부분 틀립니다.
두번째: 예외처리 .이 한개일때 굳이 방향을 바꿀일이 없으니까 0으로 처리해주기 이것
처음 . 인 좌표에서 출발해서 그곳에서 모든 방향을 통해 움직입니다.
소스코드 :
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
|
//By 콩순이냉장고
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <cstdio>
#include <cstring>
using namespace std;
int dy[4] = { -1, 0, 1, 0 };
int dx[4] = { 0, 1, 0, -1 };
int n, m;
char board[31][31];
int visit[31][31];
int result;
bool isrange(int y, int x){
if (0 <= y&&y < n && 0 <= x&&x < m)
return true;
return false;
}
void backtrack(int y, int x, int space, int dir, int cnt = 1){
if (space == 0){//모든점을 방문
result = min(cnt, result);
return;
}
int ny = y + dy[dir];
int nx = x + dx[dir];
if (isrange(ny, nx) && visit[ny][nx] == 0 && board[ny][nx] == '.'){//직선적으로 움직일수있다면 움직임
visit[ny][nx] = 1;
backtrack(ny, nx, space - 1, dir, cnt);
visit[ny][nx] = 0;
}
else{//직선으로 더이상 움직이지못함 방향을 바꿔 움직임
for (int i = 0; i < 4; i++){
if (i == dir)//방향을 바꿔야하기때문에 이전방향과 같은방향이어서는 안됨
continue;
ny = y + dy[i];
nx = x + dx[i];
if (isrange(ny, nx) && visit[ny][nx] == 0 && board[ny][nx] == '.'){
visit[ny][nx] = 1;
backtrack(ny, nx, space - 1, i, cnt + 1);
visit[ny][nx] = 0;
}
}
}
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
//freopen("input.txt", "r", stdin);
int test = 1;
while (cin >> n >> m){
result = 1e+9; //작은값으로 초기화
int space = 0; // .의 갯수
for (int i = 0; i < n; i++){
for (int j = 0; j < m; j++){
cin >> board[i][j];
if (board[i][j] == '.')
space++;
}
}
if (space == 1){//예외처리
printf("Case %d: %d\n", test++, 0);
continue;
}
for (int i = 0; i < n; i++){
for (int j = 0; j < m; j++){
if (board[i][j] == '.'){
for (int k = 0; k < 4; k++){
visit[i][j] = 1;
backtrack(i, j, space - 1, k);
visit[i][j] = 0;
}
}
}
}
printf("Case %d: %d\n", test++, result == 1e+9 ? -1 : result);
}
}
|
cs |
궁금한점 혹은 모르는점 있다면 언제든지 댓글을 이용해주시길 바랍니다.
'백준' 카테고리의 다른 글
| 벡즌 1929 소수 구하기 (0) | 2021.01.01 |
|---|---|
| 백준 16938 캠프 준비 (0) | 2020.12.31 |
| 백준 12931 두 배 더하기 (0) | 2020.12.31 |
| 백준 16953 A → B (2) | 2020.12.27 |
| 백준 1107 리모컨 (0) | 2020.11.29 |