문제
입출력
시행 착오
처음에 dfs인줄 알고 dfs로 풀어봤는데,
배열[3][0]까지 다 훑고 다음으로 배열[0][1] 부터 다시 배열 [3][1]까지 훑고 다시 배열 [0][2] 이런식으로 훑고 지나가서 구현 실패했다..
그래서 bfs로 다시 풀어보려고 했는데
나 dfs, bfs 2일차... 응애
queue에 배열을 넣어야하나,,? 근데 어떻게 넣어,,?
1차원 배열밖에 다뤄보지 않아서 구글링했다..
실패 코드
dfs
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main {
static boolean visited[][];
static int arr[][];
static int nowX, nowY, N, M;
static int dicX[] = {0, 0, -1, 1};
static int dicY[] = {-1, 1, 0, 0};
static int number = 2;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
arr = new int[N][M];
visited = new boolean[N][M];
for (int i = 0; i < N; i++) {
String str = br.readLine();
for (int j = 0; j < M; j++) {
arr[i][j] = Character.getNumericValue(str.charAt(j));
}
}
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
if(visited[i][j] == false && arr[i][j] == 1) {
dfs(i, j);
}
}
}
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
System.out.print(arr[i][j]);
}
System.out.println();
}
}
static void dfs(int x, int y) {
visited[x][y] = true;
for (int i = 0; i < 4; i++) {
nowX = dicX[i] + x;
nowY = dicY[i] + y;
if (Range_check() && visited[nowX][nowY] == false && arr[nowX][nowY] == 1) {
arr[nowX][nowY] = number;
visited[nowX][nowY] = true;
}
}
if (Range_check()){
number+=1;
dfs(nowX, nowY);
}
}
static boolean Range_check(){
return(nowX >= 0&& nowX < N && nowY >=0 && nowY < M);
}
}구현 코드
bfs
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main {
//백준 2178번 미로
static boolean visited[][];
static int arr[][];
static int N, M;
static int dicX[] = {-1, 1, 0, 0}; //상하
static int dicY[] = {0, 0, -1, 1}; //좌우
static int number = 2;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
arr = new int[N][M];
visited = new boolean[N][M];
for (int i = 0; i < N; i++) {
String str = br.readLine();
for (int j = 0; j < M; j++) {
arr[i][j] = Character.getNumericValue(str.charAt(j));
}
}
visited[0][0] = true;
bfs(0,0);
System.out.println(arr[N-1][M-1]);
// for (int i = 0; i < N; i++) {
// for (int j = 0; j < M; j++) {
// System.out.print(arr[i][j]);
// }
// System.out.println();
// }
}
static void bfs(int x, int y) {
Queue<int[]>q = new LinkedList<>();
q.add(new int[] {x,y});
while(!q.isEmpty()){
int now[] = q.poll();
int nowx = now[0];
int nowy = now[1];
for(int i = 0; i<4; i++){
int nextX = nowx+dicX[i];
int nextY = nowy+ dicY[i];
if(nextX < 0|| nextY < 0 || nextX >= N || nextY >= M)
continue;
if(visited[nextX][nextY] || arr[nextX][nextY]==0)
continue;
q.add(new int[] {nextX,nextY});
arr[nextX][nextY] = arr[nowx][nowy]+1;
visited[nextX][nextY] = true;
}
}
}
}다른 방식
public static void bfs(int x, int y) {
Queue<spot> q = new LinkedList<>();
q.add(new spot(x,y));
while(!q.isEmpty()) {
spot s = q.poll();
for (int i = 0; i < 4; i++) {
int nextX = s.x + moveX[i];
int nextY = s.y + moveY[i];
if (nextX < 0 || nextY < 0 || nextX >= N || nextY >= M) {
continue;
}
if (check[nextX][nextY] || arr[nextX][nextY] == 0) {
continue;
}
q.add(new spot(nextX, nextY));
arr[nextX][nextY] = arr[s.x][s.y] + 1;
check[nextX][nextY] = true;
}
}
}
}
class spot{
int x;
int y;
spot(int x, int y){
this.x = x;
this.y = y;
}
}dfs로 푼 코드이지만 시간 초과
public class Main_2178_미로탐색 {
static int[][] map;
static int n;
static int m;
static int minVal;
static boolean[][] visited;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
n = Integer.parseInt(st.nextToken());
m = Integer.parseInt(st.nextToken());
map = new int[n][m];
for(int i=0; i<n; i++) {
String s = br.readLine();
for(int j=0; j<m; j++) {
map[i][j] = s.charAt(j) - '0';
}
}
visited = new boolean[n][m];
visited[0][0] = true;
minVal = Integer.MAX_VALUE;
dfs(0, 0, 1);
System.out.println(minVal);
}
public static void dfs(int x, int y, int count) {
if(x == n-1 && y == m-1) {
minVal = Math.min(minVal, count);
return;
}
if(count > minVal) return; //가지치기 - 이미 count가 minVal보다 커졌다면 return;
//방향배열 사용하지 않고 조건문으로 4가지를 나누어 보았다.
if(x > 0 && !visited[x-1][y] && map[x-1][y] == 1) { //상
visited[x-1][y] = true;
dfs(x-1, y, count + 1);
visited[x-1][y] = false;
}
if(x < n-1 && !visited[x+1][y] && map[x+1][y] == 1) { //하
visited[x+1][y] = true;
dfs(x+1, y, count + 1);
visited[x+1][y] = false;
}
if(y > 0 && !visited[x][y-1] && map[x][y-1] == 1) { //좌
visited[x][y-1] = true;
dfs(x, y-1, count + 1);
visited[x][y-1] = false;
}
if(y < m-1 && !visited[x][y+1] && map[x][y+1] == 1) { //우
visited[x][y+1] = true;
dfs(x, y+1, count + 1);
visited[x][y+1] = false;
}
}
}느낀점
dfs, bfs 공부한지 얼마 되지는 않았지만
대충 느낌은 잡은 것 같다. 열심히 하면 되겠다! 뭐 이런 느낌?
느낌만 잡은거라 많은 문제를 풀어봐야겠다는 생각을 하였다.
기본부터