티스토리 뷰
목차
1. 벽 타기(25363)
👉 소스코드
import java.io.*;
import java.util.*;
public class Main {
static int X, Y, sX, sY, gX, gY;
static int[][] visited;
static char[][] arr;
static int[] moveX = {0, 0, -1, 1};
static int[] moveY = {-1, 1, 0, 0};
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
X = Integer.parseInt(st.nextToken());
Y = Integer.parseInt(st.nextToken());
arr = new char[X][Y];
visited = new int[X][Y];
for(int i = 0; i < X; i++) {
arr[i] = br.readLine().toCharArray();
if(String.valueOf(arr[i]).contains("S")) {
for(int j = 0; j < arr[i].length; j++) {
if(arr[i][j] == 'S') {
sX = i; sY = j;
break;
}
}
}
if(String.valueOf(arr[i]).contains("E")) {
for(int j = 0; j < arr[i].length; j++) {
if(arr[i][j] == 'E') {
gX = i; gY = j;
break;
}
}
}
Arrays.fill(visited[i], Integer.MAX_VALUE);
}
System.out.println(bfs(sX, sY));
}
public static int bfs(int x, int y) throws IOException {
PriorityQueue<Point> pq = new PriorityQueue<Point>();
pq.offer(new Point(x, y, 0));
visited[x][y] = 0;
while(!pq.isEmpty()) {
Point p = pq.poll();
if(visited[p.x][p.y] < p.count) continue;
int cnt = 0;
for(int j = 0; j < 4; j++) {
if(arr[p.x + moveX[j]][p.y + moveY[j]] == '#') {
cnt++;
}
}
cnt = cnt > 0 ? 1 : 0;
for(int i = 0; i < 4; i++) {
int nextX = p.x + moveX[i];
int nextY = p.y + moveY[i];
if(nextX < 0 || nextY < 0 || nextX >= X || nextY >= Y || arr[nextX][nextY] == '#') continue;
int cnt1 = 0;
for(int j = 0; j < 4; j++) {
if(arr[nextX + moveX[j]][nextY + moveY[j]] == '#') {
cnt1++;
}
}
cnt1 = cnt1 > 0 ? 1 : 0;
if(cnt == 1 && cnt1 == 1) {
if(visited[nextX][nextY] > visited[p.x][p.y]) {
visited[nextX][nextY] = visited[p.x][p.y];
pq.offer(new Point(nextX, nextY, visited[nextX][nextY]));
}
} else {
if(visited[nextX][nextY] > visited[p.x][p.y] + 1) {
visited[nextX][nextY] = visited[p.x][p.y] + 1;
pq.offer(new Point(nextX, nextY, visited[nextX][nextY]));
}
}
}
}
return visited[gX][gY];
}
static class Point implements Comparable<Point> {
int x;
int y;
int count;
public Point (int x, int y, int count) {
this.x = x;
this.y = y;
this.count = count;
}
@Override
public int compareTo(Point p) {
return this.count - p.count;
}
}
}- 다익스트라를 활용한 풀이방법
2. DFS 스페셜 저지(16964)
👉 소스코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.StringTokenizer;
public class Main {
static int V, index = 1;
static ArrayList<ArrayList<Integer>> arr = new ArrayList<ArrayList<Integer>>();
static int[] vArr;
static boolean[] visited;
static boolean flag = true;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
V = Integer.parseInt(st.nextToken());
vArr = new int[V + 1];
visited = new boolean[V + 1];
for(int i = 0; i < V + 1 ; i++) {
arr.add(new ArrayList<Integer>());
}
for(int i = 0; i < V - 1; i++) {
st = new StringTokenizer(br.readLine());
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
arr.get(a).add(b);
arr.get(b).add(a);
}
st = new StringTokenizer(br.readLine());
for(int i = 0; i < V; i++) {
vArr[i] = Integer.parseInt(st.nextToken());
}
dfs(1);
System.out.println(flag ? 1 : 0);
br.close();
}
public static void dfs(int start) {
if(!flag) return;
visited[start] = true;
HashSet<Integer> set = new HashSet<Integer>();
// 인접한 노드 중 방문하지 않은 노드들은 방문처리 후 set에 담는다.
// set에 담는 이유는 주어진 방문 순서와 비교하면서 탐색을 진행하는데
// 다음 방문해야 할 노드가 set에 없다면 올바르지 않은 탐색 순서이다 (방문을 해야 할 노드들이 존재하는 set)
for(int next : arr.get(start)) {
if(!visited[next]) {
visited[next] = true;
set.add(next);
}
}
int size = set.size();
for(int i = 0; i < size; i++) {
// 방문했던 노드의 인접한 노드가 담겨있는 set (방문 예정인 노드)
// 방문 순서에 있는 다음 방문할 노드를 가지고 set에 확인 없다면 올바르지 않은 방문 순서
if(set.remove(vArr[index])) {
dfs(vArr[index++]);
}else {
flag = false;
return;
}
}
}
}- 주어진 노드의 수와 간선의 정보로 올바른 탐색 경로인지를 판별하는 문제
3. BFS 스페셜 저지(16964)
👉 소스코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main {
static int V, index = 1;
static ArrayList<ArrayList<Integer>> arr = new ArrayList<ArrayList<Integer>>();
static int[] vArr;
static boolean[] visited;
static boolean flag = true;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
V = Integer.parseInt(st.nextToken());
vArr = new int[V + 1];
visited = new boolean[V + 1];
for(int i = 0; i < V + 1 ; i++) {
arr.add(new ArrayList<Integer>());
}
for(int i = 0; i < V - 1; i++) {
st = new StringTokenizer(br.readLine());
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
arr.get(a).add(b);
arr.get(b).add(a);
}
st = new StringTokenizer(br.readLine());
for(int i = 0; i < V; i++) {
vArr[i] = Integer.parseInt(st.nextToken());
}
bfs(1);
System.out.println(flag ? 1 : 0);
br.close();
}
public static void bfs(int start) {
visited[start] = true;
Queue<Integer> q = new LinkedList<Integer>();
q.offer(start);
while(!q.isEmpty()) {
if(!flag) return;
HashSet<Integer> set = new HashSet<Integer>();
int cur = q.poll();
for(int next : arr.get(cur)) {
if(!visited[next]) {
visited[next] = true;
set.add(next);
}
}
int size = set.size();
for(int i = 0; i < size; i++) {
if(set.remove(vArr[index])) {
q.offer(vArr[index++]);
}else {
flag = false;
return;
}
}
}
}
}- 2번 문제를 풀었다면 큐로 동일하게 풀이 가능한 문제 (2번 DFS 스페셜 저지 문제 참고)