Problem solving70 [BOJ] 5427. 불 (C++) 문제 건물의 일부에 불이 났고, 불은 매 초마다 동서남북 방향으로 인접한 빈 공간으로 퍼져나간다. 상근이는 동서남북 인접한 칸으로 이동할 수 있으며 1초가 걸린다. 벽을 통과할 수 없고, 불이 옮겨진 칸 또는 이제 불이 붙으려는 칸으로 이동할 수 없다. 얼마나 빨리 빌딩을 탈출할 수 있는지 구하기. 탈출할 수 없는 경우 IMPOSSIBLE 출력 생각할 것 1초마다 인접한 방향으로 퍼져나가므로 BFS를 사용하자. 반례 1) 1 5 6 *#.## #...# #...# #...# #.@.# ##### 답 : 5 아래의 조건을 잘 정의해주어야 한다. 벽이 아니고, 방문하지 않았고, 불이 없거나 불이 아직 퍼지기 전인 경우(도망칠 수 있는 경우) if (board[nx][ny] != '#' && run[nx][n.. 2023. 8. 8. [BOJ] 2630. 색종이 만들기 (C++) 문제 전체 종이가 모두 같은 색으로 칠해져 있지 않으면 가로와 세로로 중간 부분을 잘라서 똑같은 크기의 네 개의 N/2 × N/2색종이로 나눈다. 이때도 모두 같은 색으로 칠해져 있지 않으면 같은 방법으로 나눈다. 이와 같은 과정을 잘라진 종이가 모두 하얀색 또는 파란색으로 칠해져 있거나 하나의 정사각형 칸이 되어 더 이상 자를 수 없을 때까지 반복한다. 생각할 것 같은 동작을 반복하므로 재귀함수를 사용하고 같은 크기 4개로 나누는 동작을 분할 정복을 활용해보자 코드 #include #include using namespace std; int blue = 0; int white = 0; bool confirm(vector &board, int sx, int sy, int size) { // 모두 같은 색.. 2023. 8. 8. [BOJ] 14426. 접두사 찾기 (C++) 문제 입력으로 주어지는 M개 문자열 중 집합 S에 포함되어 있는 문자열 중 적어도 하나의 접두사인 것의 개수 구하기 생각할 것 문자를 앞에서부터 순차적으로 검색해서 존재여부를 판단하므로 트라이를 사용해보자 코드 #include #include using namespace std; struct Trie { Trie *node[26]; Trie() { for (int i = 0; i < 26; i++) node[i] = NULL; } ~Trie() { for (int i = 0; i < 26; i++) { if (node[i]) { delete node[i]; } } } void insert(string &str, int idx) { if (idx == str.size()) return; // 문자열 끝까지.. 2023. 8. 7. 트라이 (Trie) 문자열을 효율적이게 저장하고 탐색하는 트리 형태의 자료구조 문자열의 문자 순서대로 자식노드를 생성하는 방식이다 구조 struct Trie { Trie *node[26]; Trie() { for (int i = 0; i < 26; i++) node[i] = NULL; } ~Trie() { for (int i = 0; i < 26; i++) { if (node[i]) { delete node[i]; } } } void insert(string &str, int idx) { if (idx == str.size()) return; // 문자열 끝까지 탐색 시 종료 if (node[str[idx] - 'a'] == NULL) node[str[idx] - 'a'] = new Trie(); // 해당 문자 노드가 없.. 2023. 8. 7. 이전 1 2 3 4 5 6 7 8 ··· 18 다음
