백준 12886번 돌 그룹
문제
나의 풀이
import java.util.*;
public class Main {
public static int sum = 0;
public static boolean check[][] = new boolean[1501][1501];
public static void go(int x, int y) {
if(check[x][y]) { // 이미 방문한 경우
return;
}
check[x][y] = true;
int a[] = {x, y, sum - x - y};
for(int i = 0; i < 3; i++) {
for(int j = 0; j < 3; j++) {
if(a[i] < a[j]) {
int b[] = {x, y, sum - x - y};
b[i] += a[i];
b[j] -= a[i];
go(b[0], b[1]);
}
}
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int x = sc.nextInt();
int y = sc.nextInt();
int z = sc.nextInt();
sum = x + y + z;
if(sum % 3 != 0) {
System.out.println(0);
System.exit(0);
}
go(x, y);
if(check[sum / 3][sum / 3]) {
System.out.println(1);
} else {
System.out.println(0);
}
}
}돌의 개수들을 입력 받은 뒤, 이들의 합이 3으로 나누어 떨어지지 않으면 돌의 개수를 똑같이 만들 수 없다는 뜻이므로 바로 0을 출력시킨다.
그런 다음 dfs를 이용하여 해결한다.
dfs에서는 그룹 1번의 x개, 그룹 2번의 y개에 대하여 방문했다는 것을 check 배열에 표시해준 뒤 for문을 통해서 돌들의 개수를 비교해서 큰쪽은 작은쪽만큼 빼주고 작은쪽은 자신의개수만큼 더해준다. 그런 다음 다시 그렇게 나온 수들로 dfs를 반복시켜주면 된다.
dfs가 끝나면 check배열에 돌들의 개수의 합에서 3을 나눈 위치의 값이 모든 돌들의 개수가 똑같은 지점인데 이 값이 true라면 만들 수 있다는 것이므로 1을 출력해주고 아니라면 0을 출력해준다.
결과
백준 2206번 벽 부수고 이동하기
문제
나의 풀이
import java.util.*;
public class Main {
static class Pair {
int x, y, z;
Pair(int x, int y, int z) {
this.x = x;
this.y = y;
this.z = z;
}
}
public static int dx[] = {1, -1, 0, 0};
public static int dy[] = {0, 0, 1, -1};
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int m = sc.nextInt();
sc.nextLine();
int a[][] = new int[n][m];
int d[][][] = new int[n][m][2];
for(int i = 0; i < n; i++) {
String s = sc.nextLine();
for(int j = 0; j < m; j++) {
a[i][j] = s.charAt(j) - '0';
}
}
Queue<Pair> q = new LinkedList<Pair>();
d[0][0][0] = 1; // 시작점
q.offer(new Pair(0, 0, 0));
while(!q.isEmpty()) {
Pair p = q.poll();
int x = p.x;
int y = p.y;
int z = p.z;
for(int k = 0; k < 4; k++) {
int nx = x + dx[k];
int ny = y + dy[k];
if(nx < 0 || nx >= n || ny < 0 || ny >= m) { // 범위 벗어나는 경우
continue;
}
if(a[nx][ny] == 0 && d[nx][ny][z] == 0) { // 빈칸이면서 방문하지 않은 경우
d[nx][ny][z] = d[x][y][z] + 1; // 거리 업데이트
q.offer(new Pair(nx, ny, z));
}
if(z == 0 && a[nx][ny] == 1 && d[nx][ny][z + 1] == 0) { // 벽이면서 방문하지 않은 경우
d[nx][ny][z + 1] = d[x][y][z] + 1; // 거리 업데이트
q.offer(new Pair(nx, ny, z + 1));
}
}
}
if(d[n - 1][m - 1][0] != 0 && d[n - 1][m - 1][1] != 0) { // 부순 경우와 부수지 않은 경우 모두 방문했을 때
System.out.println(Math.min(d[n - 1][m - 1][0], d[n - 1][m - 1][1])); // 거리 최솟값 구하기
} else if(d[n - 1][m - 1][0] != 0) { // 부수지 않은 경우만 방문했을 때
System.out.println(d[n - 1][m - 1][0]);
} else if(d[n - 1][m - 1][1] != 0) { // 부순 경우만 방문했을 때
System.out.println(d[n - 1][m - 1][1]);
} else { // 도달하지 못하는 경우
System.out.println(-1);
}
}
}이 문제는 벽을 한번 부수고 지나갈 수 있기 때문에 정점의 정의가 행과 열 뿐만 아니라 벽을 부순 횟수인 k도 있어야 한다.
bfs 탐색을 진행하면서 4방향에 대하여 다음 칸이 빈칸인 경우, 벽을 부순적 없는데 다음 칸이 벽인 경우 등을 구분지어서 거리를 업데이트 해주고 큐에 정점을 넣어주는 형식으로 진행한다.
그런다음 벽을 한번 부숴서 도착한 경우와 부수지 않고 도착한 경우 중 비용이 가장 적게 든 경우를 출력시켜주면 된다.
결과
백준 14442번 벽 부수고 이동하기 2
문제
나의 풀이
import java.util.*;
public class Main {
static class Pair {
int x, y, z;
Pair(int x, int y, int z) {
this.x = x;
this.y = y;
this.z = z;
}
}
public static int dx[] = {1, -1, 0, 0};
public static int dy[] = {0, 0, 1, -1};
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int m = sc.nextInt();
int l = sc.nextInt();
sc.nextLine();
int a[][] = new int[n][m];
int d[][][] = new int[n][m][l + 1];
for(int i = 0; i < n; i++) {
String s = sc.nextLine();
for(int j = 0; j < m; j++) {
a[i][j] = s.charAt(j) - '0';
}
}
Queue<Pair> q = new LinkedList<Pair>();
d[0][0][0] = 1; // 시작점
q.offer(new Pair(0, 0, 0));
while(!q.isEmpty()) {
Pair p = q.poll();
int x = p.x;
int y = p.y;
int z = p.z;
for(int k = 0; k < 4; k++) {
int nx = x + dx[k];
int ny = y + dy[k];
if(nx < 0 || nx >= n || ny < 0 || ny >= m) { // 범위 벗어나는 경우
continue;
}
if(a[nx][ny] == 0 && d[nx][ny][z] == 0) { // 빈칸이면서 방문하지 않은 경우
d[nx][ny][z] = d[x][y][z] + 1; // 거리 업데이트
q.offer(new Pair(nx, ny, z));
}
if(z + 1 <= l && a[nx][ny] == 1 && d[nx][ny][z + 1] == 0) { // 벽이면서 방문하지 않은 경우
d[nx][ny][z + 1] = d[x][y][z] + 1; // 거리 업데이트
q.offer(new Pair(nx, ny, z + 1));
}
}
}
int answer = -1;
for(int i = 0; i <= l; i++) {
if(d[n - 1][m - 1][i] == 0) { // 도달하지 못한 경우
continue;
}
if(answer == -1) {
answer = d[n - 1][m - 1][i];
} else {
answer = Math.min(answer, d[n - 1][m - 1][i]);
}
}
System.out.println(answer);
}
}1과 똑같으나 벽을 L번 부술 수 있다는 점만 다르다. 삼차원배열을 생성할 때 크기를 1번 처럼 2로하는 것이 아닌 입력 받은 l의 l + 1로 해준다. 그런다음 bfs 탐색을 할 때 벽인 경우의 조건문이 조검 다른데 아까는 z == 0인 경우였으나 지금은 z + 1의 값이 l보다 작은 경우까지 허용하게 한다.
그런 다음 최소 거리를 구할 때도 l에 대하여 for문을 돌려서 비교해서 구한다.
결과
가보자고