기본 dfs, bfs

기본 dfs

int LV = 3;        // dfs 깊이
int NUM = 6;    // dfs 경우의 수
int path[10];
 
void print(int level)
{
    for (int i = 0; i < level; i++) {
        printf("%d ", path[i]);
    }
    printf("\n");
}
 
void dfs(int level)
{
    // 최종 깊이까지 들어가면 출력하고 종료
    if (level == LV) {
        print(level);
        return;
    }
 
    // 경우의수에 따라 dfs 호출
    for (int i = 1; i <= 6; i++) {
        path[level] = i;    // 현재값 저장
        dfs(level + 1);
        path[level] = 0;    // 현재값 초기화
    }
}
 
int main()
{
    dfs(0);
 
    return 0;
}
 
 

 

기본 bfs

int map[10][10];
int visit[10][10];
int fr, re;
 
struct Node{
    int dr, dc, lev;
}buf[10*10];
 
void push(int nr, int nc, int nlv)
{
    // 빠져나올 제약조건
    if (map[nr][nc] == 0) return;
    if (visit[nr][nc] != 0) return;
 
    // queue 값에 새로운 값 설정
    buf[re].dr = nr;
    buf[re].dc = nc;
    buf[re].lev = nlv;
 
    visit[nr][nc] = nlv;
 
    // re값 다음을 위해 증가
    re++;
}
 
void bfs()
{
    int sr = 3;
    int sc = 4;
    push(sr, sc, 0);
 
    // fr는 bfs들어가기 위한 now
    // re는 bfs들어가서 queue를 증가
    while (fr < re)  {
        // 현재 now를 찾고 fr은 다음을 위해 증가
        Node now = buf[fr++];
 
        // 갈수있는 방향체크
        for (int i = 0; i < 4; ++i)  {
            for (int j = 0; j < 4; ++j)  {
                push(now.dr + dr[i], now.dc + dc[i], now.lev + 1);
            }
        }
    }
}
 

 

dfs, bfs 아이디어들

- 이어진선, 블럭 등을 위한 기본 처리

- 블럭의 모양을 나타내는 16bit 사용법 (위블럭 있음1, 오른블럭 있음2, 아래블럭4, 왼블럭8) 을 써서 모양을 결정

 

 

기본적인 이어진 선 dfs

- 기본적으로는 연결된 갯수를 sum으로 세고

- 위블럭이 있으면1, 오른블럭있으면2, 아래블럭있으면4, 왼블럭있으면8 을 써서 16bit로 블럭스타일계산, 계산된 블럭의 갯수들로 type 배열을 만들어서 저장