[TIL] 24.02.02

1. 알고리즘 문제 해결

 

 

소문난 칠공주(백준 1941):

 DFS로 탐색할 때, 행렬 내에서 여러 갈래로 나뉘어지는 것도 고려하는 방법이 없을까 하다가 문제에서 주어지는 행렬이 5*5라서 브루트 포스 및 백트래킹으로 조합을 모두 따지기로 했다. 알고리즘을 간단하게 정리하면 다음과 같다.

 

 - 25명의 학생 중 7명을 선택하는 모든 조합을 탐색한다(브루트 포스 및 백트래킹 이용). 누구를 선택했는지, 현재까지 선택된 이다솜파 학생이 몇 명인지 전역변수를 통해 관리한다.

 - 7명을 선택했을 때, 이다솜파의 학생이 4명 이상인지 확인하고 DFS를 실행한다.

 - DFS에선 7명의 학생 중 한 명을 선택해(마지막에 추가된 학생) 스택에 넣고 DFS를 진행하게 되는데, 이 때 탐색하며 스택에 담을 수 있는 경우는 인접한 자리가 방문하지 않은 7명의 학생 중 한명일 때이다. 방문한 학생의 수를 카운트 변수에 체크해뒀다가 DFS 종료 후 리턴한다.

 - DFS의 리턴 값이 7일경우, 선택된 7명의 자리가 모두 인접한 경우이므로 소문난 칠공주를 결성할 수 있다. 이를 체크한다.

 - 남은 모든 조합에 대해서도 반복하여, 모든 소문난 칠공주 결성 가능 경우의 수를 찾고 이를 출력한다.

 

#include <iostream>

#include <vector>

#include <stack>

using namespace std;

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

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

vector<vector<bool> > seat(5, vector<bool>(5, false));

vector<vector<bool> > isVisited(5, vector<bool>(5, false));

int curS = 0;

int validCase = 0;

bool isValid(int y, int x) {

    return y>=0&&y<5&&x>=0&&x<5;

}

int DFS(int y, int x) {

    vector<vector<bool> > isVisitedCopy(isVisited);

    stack<pair<int, int> > st;

    st.push({y, x});

    int cnt = 0;

    while(!st.empty()) {

        pair<int, int> cur = st.top();

        st.pop();

        if(!isVisitedCopy[cur.first][cur.second]) continue;

        cnt++;

        isVisitedCopy[cur.first][cur.second] = false;

        for(int i=0; i<4; i++) {

            int nextY=cur.first+dy[i], nextX=cur.second+dx[i];

            if(isValid(nextY, nextX) && isVisitedCopy[nextY][nextX]) {

                st.push({nextY, nextX});

            }

        }

    }

    return cnt;

}

void solve(int prev, int depth) {

    if(depth == 7) {

        if(curS>3 && DFS(prev/5, prev%5)==7) {

            validCase++;

        }

        return;

    }

    for(int i=prev+1; i<25; i++) {  

        if(seat[i/5][i%5]) {

            curS++;

        }

        isVisited[i/5][i%5] = true;

        solve(i, depth+1);

        isVisited[i/5][i%5] = false;

        if(seat[i/5][i%5]) {

            curS--;

        }

    }

}

int main() {

    char c;

    for(int i=0; i<5; i++) {

        for(int j=0; j<5; j++) {

            cin >> c;

            if(c=='S') seat[i][j]=true;

        }

    }

    solve(-1, 0);

    cout << validCase;

}

 

 

 

 

미로 탐색(백준 2178):

 탐색해야하는 크기가 작고, 시작 노드와 목적 노드도 지정돼있는 경우이기 때문에 BFS를 통해 쉽게 최단 거리를 구해낼 수 있다. 큐를 이용해 간단하게 구현해 해결했다.

 

 

 

숨바꼭질(백준 1697):

 이것도 BFS로 간단하게 풀 수 있다. 점의 위치 범위에 대한 정보만 주어지고 공간 전체에 대한 범위는 주어지지 않아서 좀 난감한 부분이 있었는데 임의로 공간 또한 0~100,000내에서 존재할 거라고 생각하고 풀었다. 물론 각 좌표들에 대해 방문 처리는 필요하며, 해주지 않으면 메모리 초과가 나게 될 것이다.

 

 

 

2. 안드로이드 공부

 

 

리사이클러뷰 구현시, ListAdapter와 DiffCallback이 아닌 레거시한 방식으로 구현할 때 유의점:

 endless scroll과 swipe refresh를 모두 지원하려고 하다가 문제가 발생. 

 java.lang.IndexOutOfBoundsException: Inconsistency detected. Invalid view holder adapter position

 

 

대강 이런 오류였는데 알고보니, notifyItemRangeInserted()를 이용해서 어댑터의 아이템을 업데이트 하다보니 생긴 문제였다. 스크롤을 통해 이미 리스트가 추가된 상태에서 스와이프를 하면 초기의 아이템만을 가져 오히려 사이즈가 작아지는데, 이 때 로직에 의해서 notifyItemRangeInserted()의 인자로 잘못된 값이 들어가고 있었다.

 

        if(diffSize>0) {
            notifyItemRangeInserted(prevSize, diffSize)
        }else if(diffSize<0) {
            notifyItemRangeRemoved(lectures.size, -diffSize)
        }

 

이와 같이 분기를 나누어 사이즈를 처리해주니 더 이상 발생하지 않았다. 기존 방식으로 리사이클러뷰를 구현한다면 유의해야할 것 같다.