반응형
C에서 C까지의 최단경로를 찾는 BFS문제이다.
최단경로를 찾을때 다익스트라 알고리즘 또한 사용가능하지만, 이 문제에선 BFS를 사용하여 구현하였다. 이 문제는 자신의 방향과 방향전환횟수를 알고있어야해서 Pos라는 class에 담아둔 상태로 구현하였다. 맨처음엔 일반 visti[][] 배열을 사용하여 방문하지 않았으면 방문하고, 만일 방문했더라도 갱신이 가능하다면 다시 방문하는 방식을 사용하였다. 하지만 어느부분에서 처리가 잘되지않아 다른방법을 사용하였다. 벽을 부수고 이동하기 처럼 visit[][][] 3차원 배열을 사용하였다. 즉 visit[row][col][조건]으로 두고 풀었다. 이 문제에선 조건 부분이 방향을 뜻하는 4가지방법을 의미하여 이와같이 풀어 해결하였다.
|
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
102
103
104
105
106
107
108
109
110
111
112
113
114
|
package boj;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main_bj_6087_레이저통신_re {
static int[] di= {-1,0,1,0};
static int[] dj= {0,1,0,-1};
static int R,C;
static char[][] map;
static int[][][] visit; //-2 미방문, -1시작점, 양수는 변환횟수
static int targetI,targetJ;
static Queue<Pos> queue;
static int answer;
static class Pos{
int i,j,turn,dir;
Pos(int i,int j,int t, int d){
this.i=i;this.j=j;turn=t;dir=d;
}
}
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
C=Integer.parseInt(st.nextToken());
R=Integer.parseInt(st.nextToken());
map=new char[R][C];
visit=new int[R][C][4];
for(int i=0;i<R;i++) {
String str= br.readLine();
for(int j=0;j<C;j++) {
map[i][j]=str.charAt(j);
visit[i][j][0]=Integer.MAX_VALUE;
visit[i][j][1]=Integer.MAX_VALUE;
visit[i][j][2]=Integer.MAX_VALUE;
visit[i][j][3]=Integer.MAX_VALUE;
}
}
queue=new LinkedList<>();
bfs();
// for(int i=0;i<R;i++) {
// for(int j=0;j<C;j++) {
// System.out.print(visit[i][j][3] + " ");
// }
// }
//
answer=Integer.MAX_VALUE;
for(int i=0;i<4;i++) {
if(visit[targetI][targetJ][i]!=-Integer.MAX_VALUE) {
}
}
System.out.println(answer);
}
static void bfs() {
int count=1;
for(int i=0;i<R;i++) {
for(int j=0;j<C;j++) {
if(map[i][j]=='C' && count==1) {
count+=1;
visit[i][j][0]=-1;
visit[i][j][1]=-1;
visit[i][j][2]=-1;
visit[i][j][3]=-1;
while(!queue.isEmpty()) {
Pos cur=queue.poll();
for(int dir=0;dir<4;dir++) {
int nextI=cur.i+di[dir];
int nextJ=cur.j+dj[dir];
if(nextI<0 || nextI>=R || nextJ<0 ||nextJ>=C)
continue;
if((map[nextI][nextJ]=='.'||map[nextI][nextJ]=='C')){
visit[nextI][nextJ][dir]=cur.turn;
}
}
}
}
}
}
else if(map[i][j]=='C' && count!=1) {
targetI=i;targetJ=j;
}
}
}
}
}
http://colorscripter.com/info#e" target="_blank" style="color:#4f4f4ftext-decoration:none">Colored by Color Scripter
|
첫 번째로 시도했던 방법을 다음과 같이 구현해보았다.
|
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
102
103
104
105
106
107
108
109
110
|
package boj;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main_bj_6087_레이저통신 {
static int[] di= {-1,0,1,0};
static int[] dj= {0,1,0,-1};
static int R,C;
static char[][] map;
static int[][] visit; //-2 미방문, -1시작점, 양수는 변환횟수
static Queue<Pos> queue;
static int answer;
static int targetI,targetJ;
static class Pos{
int i,j,turn,dir;
Pos(int i,int j,int t, int d){
this.i=i;this.j=j;turn=t;dir=d;
}
}
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
C=Integer.parseInt(st.nextToken());
R=Integer.parseInt(st.nextToken());
map=new char[R][C];
visit=new int[R][C];
for(int i=0;i<R;i++) {
String str= br.readLine();
for(int j=0;j<C;j++) {
map[i][j]=str.charAt(j);
visit[i][j]=-2;
}
}
queue=new LinkedList<>();
bfs();
// for(int i=0;i<R;i++) {
// for(int j=0;j<C;j++) {
// System.out.print(visit[i][j] + " ");
// }
// }
System.out.println(visit[targetI][targetJ]);
}
static void bfs() {
boolean first=true;
for(int i=0;i<R;i++) {
for(int j=0;j<C;j++) {
if(map[i][j]=='C' &&first==true) {
first=false;
visit[i][j]=-1;
while(!queue.isEmpty()) {
Pos cur=queue.poll();
for(int dir=0;dir<4;dir++) {
int nextI = cur.i+di[dir];
int nextJ = cur.j+dj[dir];
if(nextI<0 || nextI>=R || nextJ< 0 || nextJ>=C)
continue;
if(map[nextI][nextJ]=='.'||map[nextI][nextJ]=='C') {
if(visit[nextI][nextJ]==-2) { //한번도 방문안한 지점
visit[nextI][nextJ]=cur.turn;
}
}else { //방문한 지점
visit[nextI][nextJ]=cur.turn;
}
}
}
}
}
}
else if(map[i][j]=='C' &&first==false) {
targetI=i;targetJ=j;
}
}
}
}
}
http://colorscripter.com/info#e" target="_blank" style="color:#4f4f4ftext-decoration:none">Colored by Color Scripter
|
반응형
'Algorithm' 카테고리의 다른 글
| [SWEA] 5653. 줄기세포배양 (0) | 2020.04.27 |
|---|---|
| [BOJ] 1748. 수 이어 쓰기1 (0) | 2020.04.22 |
| [BOJ] 1107. 리모컨 (0) | 2020.04.18 |
| [BOJ] 13023. ABCDE (0) | 2020.04.17 |
| [BOJ] 1260. DFS와 BFS (0) | 2020.04.17 |