프로그래머스 알고리즘 고득점 Kit - 깊이/너비 우선 탐색(DFS/BFS

타겟 넘버

- 주어진 숫자를 적절히 더하고 빼서 타겟 넘버를 만드는 방법의 수 구하기 (숫자의 순서 유지)

int answer = 0;

void dfs(vector<int>& numbers, int idx, int target, int val) {
    if(idx == numbers.size()) {
        if(val == target) answer++;
        return;
    }
    dfs(numbers, idx+1, target, val+numbers[idx]);
    dfs(numbers, idx+1, target, val-numbers[idx]);
}

int solution(vector<int> numbers, int target) {
    dfs(numbers, 0, target, 0);
    
    return answer;
}

// 재귀함수 이용하여 dfs 해버렸다..

 

네트워크

- 이차원 배열로 컴퓨터들끼리의 연결 정보가 주어졌을 때 네트워크의 개수 구하기

vector<int> graph[200];
bool visited[200] = {false};

void dfs(int v) {
    visited[v] = true;
    
    // 연결되어있는 노드들 방문
    for(int neighbor : graph[v]) {
        if(!visited[neighbor]) dfs(neighbor);
    }
}
int solution(int n, vector<vector<int>> computers) {
    // 그래프 생성
    for(int i=0; i<n; i++) {
        for(int j=0; j<n; j++) {
            if(i!=j && computers[i][j]==1) graph[i].push_back(j);
        }
    }
    
    // dfs 탐색
    int answer = 0;
    for(int i=0; i<n; i++) {
        if(!visited[i]) {
            answer++;
            dfs(i);
        }
    }
    
    return answer;
}

// 굳이 그래프 생성하지 않고도 computers 벡터를 넘겨주면서 neighbor를 확인해도 되겠다 (인접 노드 확인용)

 

게임 맵 최단거리

- 게임 뱁 상태 maps가 매개변수로 주어질 때, 상대 팀 진영에 도달하기 위해 지나야하는 칸의 개수의 최솟값 구하기

int answer, m, n;
bool visited[100][100] = {false};

void dfs(vector<vector<int>>& maps, int i, int j, int cnt) {
    if(i>=n || i<0 || j>=m || j<0) return; // 유효하지 않은 주소이거나
    if(maps[i][j]==0 || visited[i][j]) return; // 벽이 있거나, 이미 방문한 경로이면 리턴 (무한루프 방지)
    
    if(i==n-1 && j==m-1) {
        if(answer==-1) answer = cnt;
        else answer = min(answer, cnt);
        return;
    }
    
    // 인접 경로 방문해보기
    visited[i][j] = true;
    dfs(maps, i+1, j, cnt+1);
    dfs(maps, i-1, j, cnt+1);
    dfs(maps, i, j+1, cnt+1);
    dfs(maps, i, j-1, cnt+1);
    visited[i][j] = false;
}

int solution(vector<vector<int>> maps)
{
    n = maps.size(); m = maps[0].size(); answer = -1;
    dfs(maps, 0, 0, 1);
    
    return answer;
}

// 처음엔 이렇게 DFS로 풀었는데, 효율성 테스트에서 전부 시간 초과가 떴다

// '최단거리 문제'는 BFS로 풀어야한다. 어찌보면 당연한게 너비우선 탐색으로 depth를 1씩 증가시켜가며 찾으면서 목적지 도달 시 바로 return 해버리는 게 훨씬 효율적

 

int answer, m, n;
bool visited[100][100] = {false};

void bfs(vector<vector<int>>& maps) {
    queue<vector<int>> q;
    q.push(vector<int>{0,0,1}); visited[0][0] = true; // (0,0) 에서 시작
    int di[4] = {1,-1,0,0};
    int dj[4] = {0,0,1,-1};
    
    while(!q.empty()) {
        auto v = q.front(); q.pop();
        int i = v[0], j = v[1], cnt = v[2];
        
        for(int t=0; t<4; t++) {
            int new_i = i+di[t];
            int new_j = j+dj[t];
            
            if(new_i>=n || new_i<0 || new_j>=m || new_j<0) continue; // 유효하지 않은 주소거나
            if(visited[new_i][new_j] || maps[new_i][new_j]==0) continue; // 이미 방문한 주소거나(무한루프 방지) 벽이면 패스
            
            if(new_i==n-1 && new_j==m-1) {
                answer = cnt+1;
                return;
            }
            visited[new_i][new_j] = true;
            q.push(vector<int>{new_i, new_j, cnt+1});
        }
    }
}

int solution(vector<vector<int>> maps)
{
    n = maps.size(); m = maps[0].size(); answer = -1;
    bfs(maps);
    
    return answer;
}

// bfs로 풀 때에도 효율성 측면에서 크게 영향을 미치는 요소가 있었음

// 다음 방문지를 queue에 넣기 전에 visited를 미리 체크해두어야 함. queue에서 pop한 후 visited 체크하면 동일 layer에서 중복된 값이 큐에 너무 많이 들어감

 

단어 변환

- 두 단어 begin, target과 단어의 집합 words가 주어지고, 매 단계에서는 한 개의 알파벳만 바꾸고 words에 있는 단어로만 변환 가능

- 최소 몇 단계의 과정을 거쳐 begin을 target으로 변환 가능한지? => BFS

int findDiff(string s1, string s2) {
    int n = s1.length(), cnt = 0;
    for(int i=0; i<n; i++) {
        if(s1[i]!=s2[i]) cnt++;
    }
    return cnt;
}

int solution(string begin, string target, vector<string> words) {
    int diff[51][51] = {0};
    bool visited[51] = {false};
    
    int n = words.size(), fin = -1, answer = 0;
    for(int i=1; i<=n; i++) {
        diff[0][i] = findDiff(begin, words[i-1]); // begin 단어와 words 단어(1~n) 간 차이
        if(words[i-1] == target) fin = i;
        for(int j=i+1; j<=n; j++) {
            diff[i][j] = findDiff(words[i-1], words[j-1]); // words 단어(1~n) 간 차이
            diff[j][i] = diff[i][j];
        }
    }
    
    // words 안에 target이 없는 경우
    if(fin==-1) return 0;
    
    // bfs 탐색
    queue<pair<int,int>> q;
    for(int i=1; i<=n; i++) {
        if(diff[0][i] == 1) {
            if(i==fin) return 1;
            visited[i] = true;
            q.push(make_pair(i, 1));
        }
    }
    
    while(!q.empty()) {
        auto p = q.front(); q.pop();
        int idx = p.first, cnt = p.second;
        for(int i=1; i<=n; i++) {
            if(diff[idx][i] == 1 && !visited[i]) {
                if(i==fin) return cnt+1;
                visited[i] = true;
                q.push(make_pair(i, cnt+1));
            }
        }   
    }
    
    return 0;
}

// diff 배열을 생성하여 글자 수 차이를 저장해놓았다, 근데 굳이 그럴 필요 없이 매번 검사해도 될 듯

bool isOneLetterDiff(string s1, string s2) {
    int n = s1.length(), cnt = 0;
    for(int i=0; i<n; i++) {
        if(s1[i]!=s2[i]) cnt++;
    }
    return cnt==1;
}

int solution(string begin, string target, vector<string> words) { 
    int n = words.size(), answer = 0;
    bool visited[50] = {false};
    
    // bfs 탐색
    queue<pair<string, int>> q;
    q.push(make_pair(begin,0));
    
    while(!q.empty()) {
        auto p = q.front(); q.pop();
        string tmp = p.first;
        int cnt = p.second;
        if(tmp == target) {
            answer = cnt;
            break;
        }
        
        for(int i=0; i<n; i++) {
            if(isOneLetterDiff(tmp, words[i]) && !visited[i]) {
                visited[i] = true;
                q.push(make_pair(words[i], cnt+1));
            }
        }   
    }
    
    return answer;
}

// 이런 식으로 매번 isOneLetterDiff 검사하여 bfs 수행해도 됨, 굳이 diff 배열 만들 필요 없으므로 공간 효율성

 

아이템 줍기

- 최대 4개의 직사각형 정보가 담긴 rectangle 배열이 주어지고, 초기 위치와 아이템의 위치가 주어짐

- 아래 사진과 같이 직사각형 겹친 모양의 테두리를 따라서만 이동 간으할 때, 아이템 줍기 위해 이동해야 하는 최소 거리

int solution(vector<vector<int>> rectangle, int characterX, int characterY, int itemX, int itemY) {
    int grid[102][102] = {0};
    int dx[8] = {1,-1,0,0,1,1,-1,-1};
    int dy[8] = {0,0,1,-1,1,-1,1,-1};
    bool inner[102][102] = {false};
    bool visited[102][102] = {false};
    
    // 사각형이 영역 전부 색칠 (2배 해야지 너비/높이 1인 경우 테두리 구분 가능)
    for(auto r : rectangle) {
        for(int x=r[0]*2; x<=r[2]*2; x++) {
            for(int y=r[1]*2; y<=r[3]*2; y++) {
                grid[x][y] = 1;
            }
        }
    }
    
    // 테두리만 남겨놓고 비우기
    for(int x=2; x<=100; x++) {
        for(int y=2; y<=100; y++) {
            if(grid[x][y]==1) {
                bool isInner = true;
                for(int i=0; i<8; i++) if(grid[x+dx[i]][y+dy[i]]==0) isInner = false;
                inner[x][y] = isInner;
            }
        }
    }
    for(int x=2; x<=100; x++) {
        for(int y=2; y<=100; y++) {
            if(inner[x][y]) grid[x][y] = 0;
        }
    }
    
    // 최단거리 구하기 => use bfs
    queue<vector<int>> q;
    q.push(vector<int>{characterX*2, characterY*2, 0});
    visited[characterX*2][characterY*2] = true;
    while(!q.empty()) {
        auto cur = q.front(); q.pop();
        int x = cur[0], y = cur[1], moves = cur[2];
        if(x==2*itemX && y==2*itemY) {
            return moves/2;
        }
        
        for(int i=0; i<4; i++) {
            int newX = x+dx[i];
            int newY = y+dy[i];
            if(newX>=2 && newX<=100 && newY>=2 && newY<=100 && !visited[newX][newY] && grid[newX][newY]) {
                q.push(vector<int>{newX, newY, moves+1});
                visited[newX][newY] = true;
            }
        }
    }
    
    return 0;
}

// 최소 거리니까 BFS 하면 된다 (queue에는 현재 위치 + 이동 수 해서 저장해두면 될 듯)

// 테두리 정보를 담은 grid(map) 배열을 마련하고 시작 위치부터 bfs 돌리면 됨

// scale up (2배) 해야지 너비나 높이가 1인 직사각형의 마주보는 변을 구분할 수 있음!!

 

여행경로

- 주어진 항공권을 모두 한 번씩 이용하여 여행경로 구현, "ICN" 공항에서 출발하고 가능한 경로가 2개 이상일 경우 알파벳 순서가 앞서는 경로를 리턴함

set<int> used;
vector<string> answer;
bool finished = false;

void dfs(vector<vector<string>>& tickets, string curr, vector<string> path) {
    if(finished) return;
    path.push_back(curr);
    
    vector<pair<string, int>> nexts;
    for(int i=0; i<tickets.size(); i++) {
        if(tickets[i][0] == curr && used.find(i)==used.end()) {
            nexts.push_back(make_pair(tickets[i][1], i));
        }
    }
    
    if(nexts.empty()) { // 더 이상 선택할 경로가 없을 때, 모든 티켓을 소진했는지 확인
        if(used.size() == tickets.size()) {
            answer = path;
            finished = true;
            return;
        }
    }
    
    sort(nexts.begin(), nexts.end()); // 알파벳 순으로 정렬
    for(auto next : nexts) {
        // 해당 티켓 선택
        used.insert(next.second);
        
        dfs(tickets, next.first, path);
        
        // 원복
        used.erase(next.second);
    }
    
    path.erase(path.end()-1);
}

vector<string> solution(vector<vector<string>> tickets) {
    // ICN에서 시작
    dfs(tickets, "ICN", vector<string>());
    
    return answer;
}

// DFS 방식 사용, 하지만 더 이상 티켓 사용 불가능할 때 (depth 끝 도달했을 때) 해당 경로가 모든 티켓을 소진하는 유효한 경로인지 확인 필요, 아니면 다른 경로를 탐색해야 함

// 백트래킹 방식 사용, 유효한 경로가 아니면 무효화하고 다른 경로를 탐색 (재귀함수 호출 뒷부분에 원복 코드 추가)

// 알파벳 순으로 정렬된 상태에서 유효 경로 찾기 때문에 하나 찾는 순간 finished 플래그 활성화, 이후 경로들 무시

 

퍼즐 조각 채우기

- 게임 보드의 빈 공간에 퍼즐 조각을 적절히 올려놓을 때, 채울 수 있는 최대 칸 수를 구하기

- 0/90/180/270도 회전 가능하고, 각 빈칸에는 해당 빈칸을 완전히 채우는 퍼즐 한 조각씩 놓을 수 있음.

#include <string>
#include <vector>

using namespace std;

vector< vector<vector<int>> > puzzles; // 퍼즐 정보
vector< vector<int> > puzzles_info; // 좌상단 (i,j)좌표, 우하단 (i,j) 좌표, 블록개수
vector<vector<int>> blanks; // 빈칸 정보
int puzzleNum = 0, N;
int minI, maxI, minJ, maxJ, blocks;
bool used[500] = {false}; // 충분히 크게 해야 됨! (200 했을 땐 세그폴트 떴음..)

int di[4] = {-1,1,0,0};
int dj[4] = {0,0,1,-1};

bool validAddr(int i, int j) {
    if(i<0 || i>=N || j<0 || j>=N) return false;
    return true;
}

void dfs(vector<vector<int>>& table, int i, int j) {
    // 퍼즐 조각 찾기 위한 dfs
    if(minI>i) minI = i; if(maxI<i) maxI = i;
    if(minJ>j) minJ = j; if(maxJ<j) maxJ = j;
    blocks++;
    
    puzzles[puzzleNum][i][j] = 1;
    table[i][j] = 0;
    
    int newI, newJ;
    for(int t=0; t<4; t++) {
        newI = i+di[t];
        newJ = j+dj[t];
        if(validAddr(newI, newJ) && table[newI][newJ]==1) dfs(table, newI, newJ);
    }
}

void dfs2(vector<vector<int>>& game_board, int i, int j) {
    // 빈칸 찾기 위한 dfs
    if(minI>i) minI = i; if(maxI<i) maxI = i;
    if(minJ>j) minJ = j; if(maxJ<j) maxJ = j;
    blocks++;
    
    blanks[i][j] = 1;
    game_board[i][j] = 1;
    
    int newI, newJ;
    for(int t=0; t<4; t++) {
        newI = i+di[t];
        newJ = j+dj[t];
        if(validAddr(newI, newJ) && game_board[newI][newJ]==0) dfs2(game_board, newI, newJ);
    }
}

void initialize() {
    minI = minJ = N-1; maxI = maxJ = 0; blocks = 0;
    for(int i=0; i<N; i++) {
        for(int j=0; j<N; j++) {
            blanks[i][j] = 0;
        }
    }
}

int findPuzzle() {
    int p_x, p_y, b_x, b_y, p_minI, p_maxI, p_minJ, p_maxJ;
    bool same1, same2, same3, same4;
    for(int idx=0; idx<puzzleNum; idx++) {
        // 한 조각씩 검사함
        if(used[idx]) continue;
        if(puzzles_info[idx][4] != blocks) continue;
        
        p_minI = puzzles_info[idx][0]; p_minJ = puzzles_info[idx][1];
        p_maxI = puzzles_info[idx][2]; p_maxJ = puzzles_info[idx][3];
        p_x = p_maxI - p_minI; p_y = p_maxJ - p_minJ;
        b_x = maxI - minI; b_y = maxJ - minJ;
        
        same1 = same2 = same3 = same4 = false;
        if(p_x == b_x && p_y == b_y) {
            // 0도 회전, 180도 회전
            same1 = same2 = true;
            for(int di=0; di<=p_x; di++) {
                for(int dj=0; dj<=p_y; dj++) {
                    if(puzzles[idx][p_minI+di][p_minJ+dj] != blanks[minI+di][minJ+dj]) same1 = false;
                    if(puzzles[idx][p_minI+di][p_minJ+dj] != blanks[maxI-di][maxJ-dj]) same2 = false;
                }
            }
        }
        if(p_x == b_y && p_y == b_x) {
            // 90도 회전, 270도 회전
            same3 = same4 = true;
            for(int di=0; di<=p_x; di++) {
                for(int dj=0; dj<=p_y; dj++) {
                    if(puzzles[idx][p_minI+di][p_minJ+dj] != blanks[minI+dj][maxJ-di]) same3 = false;
                    if(puzzles[idx][p_minI+di][p_minJ+dj] != blanks[maxI-dj][minJ+di]) same4 = false;
                }
            }

        }
        if(same1 || same2 || same3 || same4) {
            used[idx] = true;
            return puzzles_info[idx][4];
        }
    }
    
    return 0;
}

int solution(vector<vector<int>> game_board, vector<vector<int>> table) {
    int answer = 0;
    N = game_board.size();
    
    // puzzle 초기화
    for(int i=0; i<N; i++) {
        for(int j=0; j<N; j++) {
            if(table[i][j]) {
                puzzles.push_back(vector<vector<int>>(N, vector<int>(N,0)));
                minI = minJ = N-1; maxI = maxJ = 0; blocks = 0;
                dfs(table, i, j);
                puzzles_info.push_back(vector<int>{minI, minJ, maxI, maxJ, blocks});
                puzzleNum++;
            }
        }
    }
    
    // 이제 gameboard를 탐색하며 확인!!
    int CNT = 0;
    blanks = vector<vector<int>>(N, vector<int>(N,0));
    for(int i=0; i<N; i++) {
        for(int j=0; j<N; j++) {
            if(game_board[i][j]==0) {
                // gameboard의 비어있는 공간 확인
                initialize();
                dfs2(game_board, i, j);
                
                // 적합한 퍼즐조각이 있는지 탐색
                answer += findPuzzle();
            }
        }
    }
    
    return answer;
}

 

// 빡구현문제... 

// 각 퍼즐 조각 상태를 puzzles 벡터에 저장하고, puzzles_info 벡터에는 범위 정보와 타일 갯수를 저장해둠

// gameboard를 탐색하며 빈칸을 찾는다, 각 빈칸에 대해 사용하지 않은 퍼즐 조각 중 돌려서 맞는 것이 있나 확인

// 돌려서 맞는지 확인하기 위해 빈칸의 범위 정보(i/j 좌표의 최대 최솟값)와 파일 조각의 범위 정보(i/j 좌표의 최대 최솟값)을 별도로 저장해두어야 함. 해당 범위 내에서 동일한지 확인하면 된다

 

troubleshoot1.

findPuzzle에서 두 if문을 if - else if 로 구성했는데, 들어갈 수 있는 퍼즐 조각을 불가능하다고 판단하는 경우가 있었음.

=> 가로 = 세로인 퍼즐 조각에서 90도 돌려야 들어가지는데, 첫번째 if문에서 0도 혹은 180도 돌려보고 안된다고 판단했던 거였음

=> if문 두 개로 구성함

 

troubleshoot2.

퍼즐 조각의 개수를 알 방법이 없음. 일부 테케에서 세그폴트가 떠서 인덱스 문제라고 추측

=> 만약 50*50 그리드에서 1개짜리 퍼즐조각이 엄청 많다면 puzzleNum은 충분히 200을 넘어갈 수 있겠구나 생각함.

=> bool used[500]; 이렇게 원소 갯수를 더 늘려줌