https://www.acmicpc.net/problem/9944
9944번: NxM 보드 완주하기
문제 N×M 보드 위에서 할 수 있는 게임이 있다. 보드는 크기가 1×1인 정사각형 칸으로 나누어져 있다. 보드의 각 칸은 빈 칸 또는 장애물이다. 장애물은 아래 그림에선 어두운 사각형으로 표시되어져 있다. 게임을 시작하려면 보드의 빈 칸 위에 공을 하나 놓아야 한다. 아래 그림에서 공은 회색 점으로 표시되어져 있다. 게임은 단계로 이루어져 있고, 각 단계는 아래와 같이 구성되어져 있다. 위, 아래, 오른쪽, 왼쪽 중 방향 하나를 고른 다음, 그 방향으로
www.acmicpc.net
|
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
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
|
#define _CRT_SECURE_NO_WARNINGS
#define NSIZE 31
#define MSIZE 31
#include<stdio.h>
#include<string.h>
#include<iostream>
using namespace std;
char input[NSIZE][MSIZE];
int chk[NSIZE][MSIZE];
int N, M;
int dy[] = { 0,1,0,-1 };
int dx[] = { 1,0,-1,0 };
int Min = 0x7fffffff;
int flag = 0;
int M1 = 0;
void chk1() {
int m = 0x80000000;
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
if (m <chk[i][j]) m = chk[i][j];
if (input[i][j] != '*' && chk[i][j] == 0)return;
}
}
if (Min > m) Min = m;
flag = 1;
}
void dfs(int y, int x, int cnt,int beforDir,int Tcnt) {
if (cnt == M1) {
if (Min > Tcnt)Min = Tcnt;
return;
}
int ny = y + dy[beforDir];
int nx = x + dx[beforDir];
if (0 <= ny && ny < N && 0 <= nx && nx < M&& chk[ny][nx] == 0 && input[ny][nx] != '*') {
chk[ny][nx] = Tcnt;
dfs(ny, nx, cnt+1, beforDir,Tcnt);
chk[ny][nx] = 0;
}
else {
for (int dir = 0; dir < 4; dir++) {
if (beforDir == dir)continue;
int ny = y + dy[dir];
int nx = x + dx[dir];
if (0 <= ny && ny < N && 0 <= nx && nx < M) {
if (chk[ny][nx] == 0 && input[ny][nx] != '*') {
chk[ny][nx] = Tcnt+1;
dfs(ny, nx, cnt + 1, dir, Tcnt + 1);
chk[ny][nx] = 0;
}
}
}
}
}
void searchPos() {
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
if (input[i][j] == '.') {
chk[i][j] = 1;
for (int dir = 0; dir < 4; dir++) {
chk[i][j] = 1;
dfs(i, j,1,dir,1);
chk[i][j] = 0;
}
}
}
}
}
int main(void) {
int cnt = 0;
while (cin >> N >> M) {
memset(input, 0, sizeof(input));
memset(chk, 0, sizeof(chk));
M1 = 0;
for (int i = 0; i < N; i++) {
cin >> input[i];
}
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
if (input[i][j] == '.')M1++;
}
}
cnt++;
if (M1 == 1) {
Min = 0;
printf("Case %d: %d\n", cnt, Min);
}
else {
Min = 0x7fffffff;
searchPos();
if (Min == 0x7fffffff)Min = -1;
printf("Case %d: %d\n", cnt, Min);
}
}
return 0;
}
|
이문제의 포인트는 백트래킹을 할줄 알아야 풀 수 있는 문제입니다.
일단 무조건 한방향으로 가게 한뒤에 못가게되는경우나 장애물을 만나는경우 다른방향으로 움직일때만
cnt+1을 해주면 되는 것으로
한쪽방향으로가게 하는 소스입니다. 가는내내 Tcnt가 방향을 바꿀때 카운트 되는 변수 인데 증가를 하지
않게 그대로 dfs로 보내주면 됩니다. cnt+1은 나중에 현재 . 인 공간을 다 방문했는지 확인여부
파악하기위해 갈 수있는 위치에 갈때마다 +1을 해줘야 합니다.
한쪽 방향으로만 가다가 가지 못하는경우에 dfs 에서 return을 하게 되고 chk[ny][nx]=0으로 다시 초기화하고
현재 들어온 방향과 다른 방향을 넣어주고 또 깊이 들어가게 해주면 결과적으로 알아서 최소로 가는 거리를
뽑아서 나오게 됩니다.
구현할때 좀 복잡할 수 있지만 경우를 나눠서 잘 구현하면 엄청 어려운 문제는 아닌것 같습니다.
오늘은 간단히 설명드렸고 질문이 있으시면 댓글 남겨주세요.
'알고리즘 모음집 > 알고리즘 (Algorithm)' 카테고리의 다른 글
| 백준 3085 사탕게임 (0) | 2019.10.08 |
|---|---|
| 백준 14395 4연산 (0) | 2019.10.08 |
| 백준 2234 성곽 (0) | 2019.10.07 |
| 백준 2422 한윤정이 이탈리아에 가서 아이스크림을 (0) | 2019.10.07 |
| 백준 1107 리모컨 (0) | 2019.10.04 |
댓글