백준 2178 : 미로탐색
import java.io.*;
import java.util.*;
class xy{
int x;
int y;
public xy(int x, int y){
this.x=x;
this.y=y;
}
}
public class Main {
static Scanner scan=new Scanner(System.in);
static int[][] arr;
static int[][] visited;
static int[] dx= {-1,0,0,1};
static int[] dy= {0,-1,1,0};
static int n;
static int m;
static int cnt;
public static void main(String[] args) {
n=scan.nextInt();
m=scan.nextInt();
arr=new int[n+1][m+1];
visited=new int[n+1][m+1];
for(int i=1;i<n+1;i++) {
String str=scan.next();
for(int j=1;j<m+1;j++) {
arr[i][j]=str.charAt(j-1)-'0';
}
}
BFS(1,1);
}
public static void BFS(int i,int j) {
Queue<xy> q=new LinkedList<>();
visited[i][j]=1;
q.offer(new xy(i,j));
while(!q.isEmpty()) {
xy xy=q.poll();
for(int k=0;k<4;k++) {//순서대로 위 왼 오 아래 순으로 탐색
int nextx=xy.x+dx[k];
int nexty=xy.y+dy[k];
if(nextx<1||nextx>n||nexty<1||nexty>m) {
continue;
}
if(arr[nextx][nexty]==1&&visited[nextx][nexty]==0) {
q.offer(new xy(nextx,nexty));
visited[nextx][nexty]=visited[xy.x][xy.y]+1;
}
}
}
System.out.println(visited[n][m]);
}
}아직 bfs 구현과 격자식으로 푸는게 미숙해서 힐끔거리면서 풀었다. 알고리즘 자체는 그냥 bfs통해 탐색하면 되는 문제였는데 거리를 세릴때 dfs 였다면 인자에 cnt붙여서 세면 됐었기 때문에 똑같이 했더니 안됐다.
연결되어있는 노드끼리 visited ++ 해주면서 n,m에 도착했을 때의 값을 출력하면 됐다.
다음에 다시 푼다면 까먹을 것 같다.
백준 16918 : 봄버맨
package codeup100;
import java.io.*;
import java.util.*;
public class Main {
static Scanner scan=new Scanner(System.in);
static int r,c,n;
static char[][] arr;
static int[] dx= {-1,0,0,1};
static int[] dy= {0,-1,1,0};
public static void main(String[] args) {
r= scan.nextInt(); //x
c=scan.nextInt(); //y
n=scan.nextInt(); //n초가 흐른후
arr=new char[r][c];
for(int i=0;i<r;i++) {
String str=scan.next();
for(int j=0;j<c;j++) {
arr[i][j]=str.charAt(j);
}
}
solve();
}
public static void solve() {
if(n%2==1) {
System.out.println("n이 홀수일때");
for(int i=0;i<r;i++) {
for(int j=0;j<c;j++) {
System.out.print('O');
}
System.out.println();
}
return;
}
if((n/2)%2==0){
System.out.println("n이 2의 배수이고 두번째일때");
for(int i=0;i<r;i++) {
for(int j=0;j<c;j++) {
System.out.print(arr[i][j]);
}
System.out.println();
}
return;
}
//첫번째 상태 첫 폭탄 터졌을때
for(int i=0;i<r;i++) {
for(int j=0;j<c;j++) {
if(arr[i][j]=='O') {
arr[i][j]='.';
for(int k=0;k<4;k++) {
int nextx=i+dx[k];
int nexty=j+dy[k];
if(nextx>=0&&nextx<r&&nexty>=0&&nexty<c) {
arr[nextx][nexty]='.';
}
}
}
else if(arr[i][j]=='.') {
arr[i][j]='O';
}
}
}
if((n/2)%2==1) { //2의 배수이고 첫번째
System.out.println("n이 2의 배수이고 첫번째일때");
for(int i=0;i<r;i++) {
for(int j=0;j<c;j++) {
System.out.print(arr[i][j]);
}
System.out.println();
}
return;
}
}
}처음에 n이 4주기로 격자가 반복된다는것을 알아서 이런식으로 코드를 짜보았다 하지만 이렇게 짤경우 폭탄이 연속으로 되어있으면 왼쪽거터질때 오른쪽꺼도 같이터져서 원하는 답을 구할수가 없다.ㅠㅠ 그리고 dfs bfs로 푸는게 답인건가..?흠
import java.io.*;
import java.util.*;
public class Main {
static Scanner scan=new Scanner(System.in);
static int r,c,n;
static char[][] arr;
static int[][] time; //폭탄터질때까지 남은시간
static int[] dx= {-1,0,0,1};
static int[] dy= {0,-1,1,0};
static int cnt;
public static void main(String[] args) {
r= scan.nextInt(); //x
c=scan.nextInt(); //y
n=scan.nextInt(); //n초가 흐른후
arr=new char[r][c];
time=new int[r][c];
for(int i=0;i<r;i++) {
String str=scan.next();
for(int j=0;j<c;j++) {
arr[i][j]=str.charAt(j);
if(arr[i][j]=='O') {
time[i][j]=3;
}
}
}
while(cnt++<n) {
if(cnt%2==0) { // 폭탄을 놓을 경우
for(int i=0;i<r;i++) {
for(int j=0;j<c;j++) {
if(arr[i][j]=='.') {
arr[i][j]='O';
time[i][j]=cnt+3; //놓인다음부터 3초
}
}
}
}
else if(cnt%2==1){
//폭탄을 터뜨리는 경우
for(int i=0;i<r;i++) {
for(int j=0;j<c;j++) {
if(time[i][j]==cnt) { //시간이 다된 폭탄이면
arr[i][j]='.';
for(int k=0;k<4;k++) {
int nextx=i+dx[k];
int nexty=j+dy[k];
if(nextx<0||nextx>=r||nexty<0||nexty>=c) {continue;}
if(arr[nextx][nexty]=='O'&&time[nextx][nexty]!=cnt)//터트릴 시간과 같으면 터트리지 않음, 원래 .ㅇㅣ면 바꿀필요없이 그대로놔둠
{
arr[nextx][nexty]='.';
time[nextx][nexty]=0;
}
}
}
}
}
}
}
for(int i=0;i<r;i++) {
for(int j=0;j<c;j++) {
System.out.print(arr[i][j]);
}
System.out.println();
}
}
}이렇게 time 배열에 시간을 기록하고 터뜨릴때 시간을 보고 터뜨려야한다. 그리고 연쇄로 지금 시간에 터질 폭탄이 터지지않도록 코드를 짜주어야한다.
다시 풀라면 못풀것같으니까 다시풀어보자!!
백준 7562 : 나이트의 이동
import java.io.*;
import java.util.*;
class xy{
int x;
int y;
public xy(int x, int y) {
this.x=x;
this.y=y;
}
}
public class Main {
static Scanner scan=new Scanner(System.in);
static int[][] arr;
static int l,a,b,x,y;
static int[] dx= {2,2,1,1,-1,-1,-2,-2};
static int[] dy= {1,-1,-2,2,-2,2,-1,1};
static int[][] visited;
public static void main(String[] args) {
int t=scan.nextInt(); //테스트케이스의 개수
for(int m=0;m<t;m++) {
l=scan.nextInt(); //체스판 한변의 길이
a=scan.nextInt(); //현재위치 (a,b)
b=scan.nextInt();
x=scan.nextInt(); // 가고싶은 위치(x,y)
y=scan.nextInt();
visited=new int[l][l];
bfs();
}
}
public static void bfs() {
Queue<xy> q=new LinkedList<>();
q.offer(new xy(a,b));//시작점
if(a==x&&b==y) {
System.out.println("0");
return;
}
while(!q.isEmpty()) {
xy xy=q.poll();
if(xy.x==x&&xy.y==y) {
System.out.println(visited[x][y]);
break;
}
for(int i=0;i<8;i++) {
int nextx=xy.x+dx[i];
int nexty=xy.y+dy[i];
if(nextx<0||nexty<0||nextx>=l||nexty>=l) continue;
if(visited[nextx][nexty]==0) {
q.offer(new xy(nextx,nexty));
visited[nextx][nexty]=visited[xy.x][xy.y]+1;
}
}
}
}
}처음에는 설마 나이프가 갈수있는 8개의 경로 모두 경우의 수로 따지는게 답인가 했는데 진짜 그게 답이였다.. 좀 방대하게 반복문을 돌리게 되면 이게 답이 아닌것같아 이게 맞나..?하는 상태가 되는데 일단 그렇게해도 답은 나올 수 있으니까 일단 답부터내고 보자 ㅎㅎ.. 위의 미로탐색에서 bfs를 제대로 구현했다면 다시풀필요는 x
백준 7576 :토마토
import java.io.*;
import java.util.*;
class xy{
int x;
int y;
public xy(int x,int y){
this.x=x;
this.y=y;
}
}
public class Main {
static Scanner scan=new Scanner(System.in);
static int[][] arr;
static int m,n,x,y,max;
static int[] dx= {1,0,0,-1};
static int[] dy= {0,-1,1,0};
static int[][] visited;
static Queue<xy> q=new LinkedList<>();
public static void main(String[] args) {
m=scan.nextInt();//가로
n=scan.nextInt();//세로
arr=new int[n][m];
for(int i=0;i<n;i++) {
for(int j=0;j<m;j++) {
arr[i][j]=scan.nextInt();
if(arr[i][j]==1) {
q.offer(new xy(i,j));
}
}
}
//모든 판을 탐색 : q에 두개씩 한번에 넣어서 다 poll한다음에 next꺼
while(!q.isEmpty()) {
xy xy=q.poll();
for(int i=0;i<4;i++) {
int nextx=xy.x+dx[i];
int nexty=xy.y+dy[i];
if(nextx<0||nexty<0||nextx>=n||nexty>=m||arr[nextx][nexty]!=0) continue;
arr[nextx][nexty]=arr[xy.x][xy.y]+1;
q.offer(new xy(nextx,nexty));
}
}
if(check()) {
System.out.println(max-1);
}
else
{
System.out.print(-1);
}
}
public static boolean check() {
for(int i=0;i<n;i++) {
for(int j=0;j<m;j++) {
//안익은 토마토가 있을때
if(arr[i][j]==0) {
return false;
}
//날짜 최종인 곳 구하기
max=Math.max(max, arr[i][j]);
}
}
return true;
}
}탐색을 시작하는 좌표가 여러개인 경우의 문제이다. 시작하는 좌표를 일단 queue에 다 넣어버리고 차례로 탐색을 시작하면 된다! 잘 기억이 안난다면 다시풀어봐도 되고 기억이 난다면 다시 안풀어도 된다.
1697 : 숨바꼭질
그래프 창조 문제이다.
import java.io.*;
import java.util.*;
public class Main {
static Scanner scan=new Scanner(System.in);
static int[][] arr;
static int k,n,x,y,max;
static int[] visited;
static Queue<Integer> q=new LinkedList<>();
public static void main(String[] args) {
n=scan.nextInt();
k=scan.nextInt();
visited=new int[100001];
if(n==k) {
System.out.print(0);
}
else {
q.offer(n);
while(!q.isEmpty()) {
int a=q.poll();
if(a==k) {//동생을 잡으면
System.out.print(visited[k]);
}
//왼쪽으로 한칸
if(a-1>=0&&visited[a-1]==0) {
q.offer(a-1);
visited[a-1]=visited[a]+1;
}
//오른쪽으로 한칸
if(a+1<=100000&&visited[a+1]==0) {
q.offer(a+1);
visited[a+1]=visited[a]+1;
}
//오른쪽으로 곱하기 2칸
if(a*2<=100000&&visited[a*2]==0) {
q.offer(a*2);
visited[a*2]=visited[a]+1;
}
}
}
}
}같은 위치에있을 때 예외처리 안한 것 배열의 범위 잘못지정 (큰것=>같거나 큰것) 해서 제출 여러번했다. 그리고 처음에 아이디어가 떠오르지 않아서 블로그 참고.
만약에 어떻게 풀지 모르겠으면 다시풀어보기! 어떻게 풀지 그려지만 풀지말기
숨바꼭질 4 풀기 !! 이거말고
연속으로 bfs푸니까 또 dfs 구현이 기억안나려고 한다 ^^ ...
13913 : 숨바꼭질4
import java.io.*;
import java.util.*;
public class Main {
static Scanner scan=new Scanner(System.in);
static int[][] arr;
static int k,n,x,y,max;
static int[] visited;
static int[] parent;
static Queue<Integer> q=new LinkedList<>();
static StringBuilder sb=new StringBuilder();
public static void main(String[] args) {
n=scan.nextInt();
k=scan.nextInt();
visited=new int[100001];
parent=new int[100001];
if(n==k) {
System.out.println(0);
System.out.print(n);
}
else {
q.offer(n);
while(!q.isEmpty()) {
int a=q.poll();
if(a==k) {//동생을 잡으면
System.out.println(visited[k]);
}
//왼쪽으로 한칸
if(a-1>=0&&visited[a-1]==0) {
q.offer(a-1);
parent[a-1]=a;
visited[a-1]=visited[a]+1;
}
//오른쪽으로 한칸
if(a+1<=100000&&visited[a+1]==0) {
q.offer(a+1);
parent[a+1]=a;
visited[a+1]=visited[a]+1;
}
//오른쪽으로 곱하기 2칸
if(a*2<=100000&&visited[a*2]==0) {
q.offer(a*2);
parent[a*2]=a;
visited[a*2]=visited[a]+1;
}
}
//출력
Stack<Integer> s=new Stack<>();
int idx=k;
while(idx!=n) {
s.push(idx);
idx=parent[idx];
}
s.push(idx);
while(!s.isEmpty()) {
System.out.print(s.pop()+" ");
}
}
}
}기본코드는 숨바꼭질1과 같고
parent라는 배열을 한개 더 만들어서 index의 부모노드를 배열 값에 저장했다.
그리고 도착지인 k 부터 거꾸로 찾아내려가면서 출력한다. 처음에는 sb에 넣었는데 거꾸로 나와서 stack에 넣었다. 숨바꼭질 1 말고 4를 풀자
백준 13549 : 숨바꼭질 3
import java.io.*;
import java.util.*;
public class Main {
static Scanner scan=new Scanner(System.in);
static int[][] arr;
static int k,n,x,y,max;
static int[] visited;
static int[] cnt;
static Queue<Integer> q=new LinkedList<>();
static StringBuilder sb=new StringBuilder();
public static void main(String[] args) {
n=scan.nextInt();
k=scan.nextInt();
visited=new int[100001];
cnt=new int[100001];
if(n==k) {
System.out.println(0);
}
else {
q.offer(n);
while(!q.isEmpty()) {
int a=q.poll();
if(a==k) {//동생을 잡으면
System.out.println(cnt[k]);
}
//오른쪽으로 곱하기 2칸
if(a*2<=100000&&visited[a*2]==0) {
q.offer(a*2);
cnt[a*2]=cnt[a];
visited[a*2]=visited[a]+1;
}
//왼쪽으로 한칸
if(a-1>=0&&visited[a-1]==0) {
q.offer(a-1);
cnt[a-1]=cnt[a]+1;
visited[a-1]=visited[a]+1;
}
//오른쪽으로 한칸
if(a+1<=100000&&visited[a+1]==0) {
q.offer(a+1);
cnt[a+1]=cnt[a]+1;
visited[a+1]=visited[a]+1;
}
}
}
}
}순간이동 하는경우가 가중치가 0이기때문에 우선순위가 높아 순간이동을 먼저 해주면 정답처리가 되는데 잘 이해가 안간다 ㅠㅠㅠ.... 다익스트라 알고리즘을 공부한 후에도 이해가 안되는지 함보자..
참고블로그
https://loosie.tistory.com/243
https://minkwon4.tistory.com/5
=> 0-1 bfs라는 개념 때문이였다
https://velog.io/@nmrhtn7898/ps-0-1-BFS
https://justicehui.github.io/medium-algorithm/2018/08/30/01BFS/
꼭 읽어보기!
남기고 싶은 개발자입니다 :>