[DFS/BFS] 마름모 모양 만들기

 

https://eboong.tistory.com/610

[*5644*] 무선 충전 in Java (Feat. SWEA)

 

위 문제를 dfs로 풀다가 막혀서

이번 기회에 DFS와 BFS로 모두 구현해보기로 결정!

---

격자 크기 : 10 X 10

길이가 4인 마름모 그리기!

---

1. DFS

(1) visited 위치가 nx, ny 기준으로 변경될 때

package day_0818;
 
public class test {
    static int[][] map=new int[10][10];
    static boolean[][] visited=new boolean[10][10];
    static int[] dxs= {-1,1,0,0};
    static int[] dys= {0,0,-1,1};
    
    public static void main(String[] args) {
        visited[5][5]=true;
        map[5][5]=1;
        dfs(5,5,0); // depth
        for (int i = 0; i < 10; i++) {
            for (int j = 0; j < 10; j++) {
                System.out.print(map[i][j]+" ");
            }
            System.out.println();
        }
    }
    private static void dfs(int x, int y,int cnt) {
        if(cnt==3) {
            return;
        }
        for (int i = 0; i < 4; i++) {
            int nx=x+dxs[i];
            int ny=y+dys[i];
            if(canGo(nx,ny)) {
                visited[nx][ny]=true;
                map[nx][ny]=1;
                dfs(nx,ny,cnt+1);
                visited[nx][ny]=false;
            }
        }
    }
    private static boolean canGo(int nx, int ny) {
        return nx>=0 && nx<10 && ny>=0 && ny<10 && !visited[nx][ny];
    }
    
 
}
 

 

 

 

(2) 

 

package test_0829;
 
public class Solution2 {
    static int[][] map=new int[100][100];
    static boolean[][] visited=new boolean[100][100];
    static int[] dxs= {-1,1,0,0};
    static int[] dys= {0,0,-1,1};
    
    public static void main(String[] args) {
        dfs(30,30,0);
        for (int i = 0; i < 100; i++) {
            for (int j = 0; j < 100; j++) {
                System.out.print(map[i][j]+" ");
            }
            System.out.println();
        }
 
    }
 
    private static void dfs(int x, int y,int cnt) {
        map[x][y]=1;
        visited[x][y]=false;
        if(cnt==6) {
            return;
        }
        for (int i = 0; i < 4; i++) {
            int nx=x+dxs[i];
            int ny=y+dys[i];
            if(canGo(nx,ny)) {
                visited[nx][ny]=true;
                dfs(nx,ny,cnt+1);
            }
        }
        
    }
 
    private static boolean canGo(int nx, int ny) {
        return nx>=0 && nx<100 && ny>=0 && ny<100 && !visited[nx][ny];
    }
 
}
 

 

 

(3)

array = [[0 for _ in range(10)] for _ in range(10)]
dxs = [-1, 1, 0, 0]
dys = [0, 0, -1, 1]

def dfs(x, y, cnt):
    if cnt == 3:
        return

    for i in range(4):
        nx = x + dxs[i]
        ny = y + dys[i]
        if can_go(nx, ny):
            array[nx][ny] = 1
            dfs(nx, ny, cnt + 1)

def can_go(x, y):
    return x >= 0 and x < 10 and y >= 0 and y < 10

dfs(5, 5, 0)
for i in range(10):
    print(*array[i])

 

---

 

2. BFS

package day_0818;
 
import java.util.ArrayDeque;
import java.util.Queue;
 
public class test {
    static int[][] map=new int[10][10];
    static boolean[][] visited=new boolean[10][10];
    static int[] dxs= {-1,1,0,0};
    static int[] dys= {0,0,-1,1};
    
    public static void main(String[] args) {
        
        bfs();
        for (int i = 0; i < 10; i++) {
            for (int j = 0; j < 10; j++) {
                System.out.print(map[i][j]+" ");
            }
            System.out.println();
        }
    }
    private static void bfs() {
        Queue<int[]> queue= new ArrayDeque<>();
        visited[5][5]=true;
        map[5][5]=1;
        queue.add(new int[]{5,5,0}); // x,y 초기값 
        
        while (!queue.isEmpty()) {
            int[] locTmp=queue.poll();
            int x=locTmp[0];
            int y=locTmp[1];
            int depth=locTmp[2];
            
            if (depth==3) break;
            for (int i = 0; i < 4; i++) {
                int nx=x+dxs[i];
                int ny=y+dys[i];
                if(canGo(nx, ny)) {
                    visited[nx][ny]=true;
                    map[nx][ny]=1;
                    queue.add(new int[] {nx,ny,depth+1});
                }
            }
        }
    }
    private static boolean canGo(int nx, int ny) {
        return nx>=0 && nx<10 && ny>=0 && ny<10 && !visited[nx][ny];
    }
    
}