본문 바로가기

Programming/BOJ

 (42)
[백준/C++] 백준 2178번: 미로탐색 (BFS) 드디어 BFS에 입문한다. 마구잡이식으로 풀기를 시작했더니 왜 BFS를 쓰는지 아직 모르겠음.. 미로탐색 당연히 DFS로 풀었더니 시간초과가 뜬다. 시간초과가 뜨는 코드는 아래와 같다. #include using namespace std; int N, M; int map[101][101]; int dx[] = { 1, 0, 0, -1 }; int dy[] = { 0, 1, -1, 0 }; int ans = 9999; void dfs(int x, int y, int cnt) { if (x == N && y == M) { if (cnt < ans) ans = cnt; } for (int i = 0; i < 4; i++) { int next_x = x + dx[i]; int next_y = y + dy[i];..
[백준/C++] 백준 1012번: 유기농 배추 배추가 있는 곳을 배열로 저장했고, 배추가 있는 곳을 찾아다니면서 dfs를 돌렸다. map에 배추가 있는 곳을 1로 표시했는데 방문하면 2로 바꿔서 다시 방문하지 않도록 했다. 자꾸 이상하게 나와서 뭐지 했는데 2를 대입해야되는데 ==표시로 하고있었다;; 하......시간날림 #include using namespace std; int map[50][50]; int dx[] = {1,0,0,-1}; int dy[] = {0,1,-1,0}; void dfs(int x, int y, int r, int c) { for (int i = 0; i = r || ..
[백준/C++] 백준 1946번: 신입 사원 별거 아닌데 문제가 이해안되서 헤맸다. 난독인듯. 서류랑 면접 순위를 나타낸건데 점수를 나타낸 건 줄 알고 계속 고뇌에 빠졌었다. 순위가 서류와 면접 두 가지로 주어지기 때문에 일단 서류/면접 중 하나로 정렬한다. 이후 아래와 같이 제일 높은 서류성적을 가진사람의 면접순위를 최대 면접순위에 저장해놓고 다음사람을 최대 면접순위와 비교하고, 최대값보다 높은 순위를 가지면 그 값으로 최대 면접순위를 업데이트 하는 식으로 풀면 된다. #include #include using namespace std; int T, N; int cnt_array[21]; pair score[100000]; int main() { cin >> T; for (int i = 0; i > N; for (i..
[백준/C++] 백준 1987번: 알파벳 조합을 찾을 때 경우의 수가 많지 않다면 DFS를 써서 완전탐색을 하면 된다. 근데 조금만 문제가 다르게 나와도 이게 잘 생각이 안난다. 1차원배열의 조합찾기 = DFS!!!를 떠올리자. ex)비밀번호 만들기 알파벳의 아스키코드를 이용해서 이미 한번 사용한 알파벳은 방문처리한다. 특이점은 모든 경로 중 제일 긴 경로를 찾아야 하므로, 방문했던 알파벳은 다른 경로를 찾을 때 다시 풀어줘야 한다는 것이다. #include using namespace std; char map[30][30]; bool visit[26]; // 알파벳의 갯수만큼 존재 -> bool변수는 전역변수로 선언시 0으로 초기화 된다. int Dr[] = {1, -1, 0, 0}; int Dc[] = {0, 0, 1, -1}; int R,..
[백준/C++] 백준 1759번 : 암호만들기 #include #include #include using namespace std; int visit[15][15]; int L, C; char key[15]; //char candidate[15]; void dfs(int start, string str, int vowel, int consonant) { //재귀함수의 종료조건 if (str.size() == L) { if (vowel >= 1 && consonant >= 2) { cout L >> C; for (int i = 0; i > key[i]; } sort(key, key + C); dfs(0, "", 0, 0); return 0; }
[백준/C++] 백준 1931번: 회의실배정 pair data type에 sort함수를 적용하면 first를 기준으로 오름차순 sorting한다. 그러므로 끝나는 시간 순으로 정렬하고 싶으면 끝나는 시간을 first에 담으면 된다. #include #include using namespace std; int main() { int N;//회의의 개수! pair meeting_time[100000]; //freopen("Text2.txt", "r", stdin); cin >> N; //first에 끝나는 시간을 넣고 second에 시작하는 시간을 넣는다. for (int i = 0; i > meeting_time[i].second >> meeting_time[i].first; } sort(meeting_time, mee..
[백준/C++] 백준 1697번: 숨바꼭질 모든 경우의 수를 담고 찾는다. #define MIN 0 #define MAX 100000 #include #include using namespace std; /* 동생이 자신보다 작은 곳에 위치할 때 탐색할 필요가 없다. N > N >> K; int pos; int cnt=0; //몇 초인지 세어야 한다. queue q; //현 위치와 시간을 넣는다. q.push(make_pair(N, cnt)); ch..
[백준/C++] 백준 1652번: 누울 자리를 찾아라 #include #include using namespace std; int N; int map[101][101]; int main() { cin >> N; char k; for (int i = 0; i > k; if (k == '.') map[i][j] = 1; else map[i][j] = 0; } } int cnt_row = 0; int row = 0; for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { if (map[i][j] == 1)cnt_row++; else cnt_row = 0; if (cnt_row == 2) row ++; } cnt_row = 0; ..

티스토리툴바