너구리의 코딩 블로그
반응형
풀이
표의 그림은 복잡해 보이지만 생각보다 간단한 BFS 문제입니다.
맵의 상태를 입력으로 받아준 뒤, 시작지점의 좌표 ( start_i, start_j, time - 1 )에서 탐색을 시작합니다.
이때 맵의 정보 (cap)을 이용하여 cap이 1 ~ 7 각각의 경우에 대해 모두 처리해주었습니다.
여기에서 주의할 점으로는, 현재 위치에서 다음 지점으로 연결되어 있다고 할지라도,
다음 지점에서도 현재 지점으로 파이프가 연결되어 있어야 이동 가능하다는 점입니다.
이 점에 주의한다면 코드는 길지만 어렵지 않게 풀이할 수 있는 문제입니다.
코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class Solution_탈주범검거 {
static int[] di = { 0, 1, 0, -1 };
static int[] dj = { 1, 0, -1, 0 };
static StringTokenizer st;
static int[][] map;
static boolean[][] visited;
static int TC, N, M, start_i, start_j, next_i, next_j, time, ans;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
TC = Integer.parseInt(br.readLine().trim());
for (int tc = 1; tc <= TC; tc++) {
st = new StringTokenizer(br.readLine().trim(), " ");
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
start_i = Integer.parseInt(st.nextToken());
start_j = Integer.parseInt(st.nextToken());
time = Integer.parseInt(st.nextToken());
map = new int[N][M];
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine(), " ");
for (int j = 0; j < M; j++) {
map[i][j] = Integer.parseInt(st.nextToken());
}
}
ans = 1;
bfs(new Pos(start_i, start_j, time - 1));
sb.append("#" + tc + " " + ans + "\n");
}
System.out.println(sb.toString());
}
static void bfs(Pos before) {
Queue<Pos> q = new LinkedList<Pos>();
q.offer(before);
visited = new boolean[N][M];
visited[before.i][before.j] = true;
while (!q.isEmpty()) {
Pos tmp = q.poll();
int cap = map[tmp.i][tmp.j];
if (cap == 1) {
for (int k = 0; k < 4; k++) {
next_i = tmp.i + di[k];
next_j = tmp.j + dj[k];
if (next_i < 0 || next_j < 0 || next_i >= N || next_j >= M)
continue;
if(k == 0 && (map[next_i][next_j] == 2 || map[next_i][next_j] == 4 || map[next_i][next_j] == 5))
continue;
else if(k == 1 && (map[next_i][next_j] == 3 || map[next_i][next_j] == 5 || map[next_i][next_j] == 6))
continue;
else if( k == 2 && (map[next_i][next_j] == 2 || map[next_i][next_j] == 6 || map[next_i][next_j] == 7))
continue;
else if( k == 3 && (map[next_i][next_j] == 3 || map[next_i][next_j] == 4 || map[next_i][next_j] == 7))
continue;
if (!visited[next_i][next_j] && tmp.dist > 0 && map[next_i][next_j] != 0) {
visited[next_i][next_j] = true;
q.offer(new Pos(next_i, next_j, tmp.dist - 1));
ans++;
}
}
} else if (cap == 2) {
for (int k = 1; k < 4; k += 2) {
next_i = tmp.i + di[k];
next_j = tmp.j + dj[k];
if (next_i < 0 || next_j < 0 || next_i >= N || next_j >= M)
continue;
if(k == 0 && (map[next_i][next_j] == 2 || map[next_i][next_j] == 4 || map[next_i][next_j] == 5))
continue;
else if(k == 1 && (map[next_i][next_j] == 3 || map[next_i][next_j] == 5 || map[next_i][next_j] == 6))
continue;
else if( k == 2 && (map[next_i][next_j] == 2 || map[next_i][next_j] == 6 || map[next_i][next_j] == 7))
continue;
else if( k == 3 && (map[next_i][next_j] == 3 || map[next_i][next_j] == 4 || map[next_i][next_j] == 7))
continue;
if (!visited[next_i][next_j] && tmp.dist > 0 && map[next_i][next_j] != 0) {
visited[next_i][next_j] = true;
q.offer(new Pos(next_i, next_j, tmp.dist - 1));
ans++;
}
}
} else if (cap == 3) {
for (int k = 0; k < 4; k += 2) {
next_i = tmp.i + di[k];
next_j = tmp.j + dj[k];
if (next_i < 0 || next_j < 0 || next_i >= N || next_j >= M)
continue;
if(k == 0 && (map[next_i][next_j] == 2 || map[next_i][next_j] == 4 || map[next_i][next_j] == 5))
continue;
else if(k == 1 && (map[next_i][next_j] == 3 || map[next_i][next_j] == 5 || map[next_i][next_j] == 6))
continue;
else if( k == 2 && (map[next_i][next_j] == 2 || map[next_i][next_j] == 6 || map[next_i][next_j] == 7))
continue;
else if( k == 3 && (map[next_i][next_j] == 3 || map[next_i][next_j] == 4 || map[next_i][next_j] == 7))
continue;
if (!visited[next_i][next_j] && tmp.dist > 0 && map[next_i][next_j] != 0) {
visited[next_i][next_j] = true;
q.offer(new Pos(next_i, next_j, tmp.dist - 1));
ans++;
}
}
} else if (cap == 4) {
for (int k = 0; k < 4; k += 3) {
next_i = tmp.i + di[k];
next_j = tmp.j + dj[k];
if (next_i < 0 || next_j < 0 || next_i >= N || next_j >= M)
continue;
if(k == 0 && (map[next_i][next_j] == 2 || map[next_i][next_j] == 4 || map[next_i][next_j] == 5))
continue;
else if(k == 1 && (map[next_i][next_j] == 3 || map[next_i][next_j] == 5 || map[next_i][next_j] == 6))
continue;
else if( k == 2 && (map[next_i][next_j] == 2 || map[next_i][next_j] == 6 || map[next_i][next_j] == 7))
continue;
else if( k == 3 && (map[next_i][next_j] == 3 || map[next_i][next_j] == 4 || map[next_i][next_j] == 7))
continue;
if (!visited[next_i][next_j] && tmp.dist > 0 && map[next_i][next_j] != 0) {
visited[next_i][next_j] = true;
q.offer(new Pos(next_i, next_j, tmp.dist - 1));
ans++;
}
}
} else if (cap == 5) {
for (int k = 0; k < 2; k++) {
next_i = tmp.i + di[k];
next_j = tmp.j + dj[k];
if (next_i < 0 || next_j < 0 || next_i >= N || next_j >= M)
continue;
if(k == 0 && (map[next_i][next_j] == 2 || map[next_i][next_j] == 4 || map[next_i][next_j] == 5))
continue;
else if(k == 1 && (map[next_i][next_j] == 3 || map[next_i][next_j] == 5 || map[next_i][next_j] == 6))
continue;
else if( k == 2 && (map[next_i][next_j] == 2 || map[next_i][next_j] == 6 || map[next_i][next_j] == 7))
continue;
else if( k == 3 && (map[next_i][next_j] == 3 || map[next_i][next_j] == 4 || map[next_i][next_j] == 7))
continue;
if (!visited[next_i][next_j] && tmp.dist > 0 && map[next_i][next_j] != 0) {
visited[next_i][next_j] = true;
q.offer(new Pos(next_i, next_j, tmp.dist - 1));
ans++;
}
}
} else if (cap == 6) {
for (int k = 1; k < 3; k++) {
next_i = tmp.i + di[k];
next_j = tmp.j + dj[k];
if (next_i < 0 || next_j < 0 || next_i >= N || next_j >= M)
continue;
if(k == 0 && (map[next_i][next_j] == 2 || map[next_i][next_j] == 4 || map[next_i][next_j] == 5))
continue;
else if(k == 1 && (map[next_i][next_j] == 3 || map[next_i][next_j] == 5 || map[next_i][next_j] == 6))
continue;
else if( k == 2 && (map[next_i][next_j] == 2 || map[next_i][next_j] == 6 || map[next_i][next_j] == 7))
continue;
else if( k == 3 && (map[next_i][next_j] == 3 || map[next_i][next_j] == 4 || map[next_i][next_j] == 7))
continue;
if (!visited[next_i][next_j] && tmp.dist > 0 && map[next_i][next_j] != 0) {
visited[next_i][next_j] = true;
q.offer(new Pos(next_i, next_j, tmp.dist - 1));
ans++;
}
}
} else if (cap == 7) {
for (int k = 2; k < 4; k++) {
next_i = tmp.i + di[k];
next_j = tmp.j + dj[k];
if (next_i < 0 || next_j < 0 || next_i >= N || next_j >= M)
continue;
if(k == 0 && (map[next_i][next_j] == 2 || map[next_i][next_j] == 4 || map[next_i][next_j] == 5))
continue;
else if(k == 1 && (map[next_i][next_j] == 3 || map[next_i][next_j] == 5 || map[next_i][next_j] == 6))
continue;
else if( k == 2 && (map[next_i][next_j] == 2 || map[next_i][next_j] == 6 || map[next_i][next_j] == 7))
continue;
else if( k == 3 && (map[next_i][next_j] == 3 || map[next_i][next_j] == 4 || map[next_i][next_j] == 7))
continue;
if (!visited[next_i][next_j] && tmp.dist > 0 && map[next_i][next_j] != 0) {
visited[next_i][next_j] = true;
q.offer(new Pos(next_i, next_j, tmp.dist - 1));
ans++;
}
}
}
}
}
static class Pos {
int i, j, dist;
public Pos(int i, int j, int dist) {
super();
this.i = i;
this.j = j;
this.dist = dist;
}
}
}
출처
https://swexpertacademy.com/main/learn/course/lectureProblemViewer.do
SW Expert Academy
SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!
swexpertacademy.com
반응형
'알고리즘 연습' 카테고리의 다른 글
| [프로그래머스] 2018 KAKAO BLIND RECRUITMENT 1차 다트 게임 (0) | 2020.03.16 |
|---|---|
| [SWEA] 2105. [모의 SW 역량테스트] 디저트 카페 JAVA 문제풀이 (0) | 2020.02.06 |
| [ SWEA ] 1949. [모의 SW 역량테스트] 등산로 조성 JAVA 문제풀이 (0) | 2020.02.03 |
| [프로그래머스_2018 KAKAO BLIND RECRUITMENT] 1차_뉴스 클러스터링 (0) | 2020.02.02 |
| [백준_BOJ] 4673. 셀프 넘버 _ JAVA (0) | 2020.01.04 |