본문 바로가기

Programming/BOJ

 (42)
[백준/C++] 14502번: 연구소 17년도 삼성기출이다. 그리 어렵지 않을 줄 알았는데 머리 좀 써야된다..흑ㅠㅠ map이 크지 않기 때문에 어디에 벽을 둘 지를 부르트포스로 찾으면 되는데 나는 이 부분이 어려웠다. 3개의 벽을 찾았을 때마다 바이러스를 퍼트리도록 하도록 코딩하면 된다. 처음에는 3개의 벽을 다 배열에 담은 다음 그 후에 각 요소에 바이러스를 퍼트리도록 짜려고 했었는데 풀고보니 배열에 굳이 담을 필요없이 그때마다 처리해주면 된다는 것을 배웠다. 문제 풀이 순서 1) 3개의 벽의 자리를 선택해 벽을 세운다. 2) 바이러스를 퍼트린다. 3) 안전구역의 갯수를 센다. 4) 이를 vector에 담는다. 5) 이를 모든 조합에 대해 반복한다. 6) vector에서 최댓값을 찾아 출력한다. #include #include #incl..
[백준/C++] 2589번: 보물섬 이문제는 딱히 까다롭지 않고 모든 시작점에 대해서 bfs를 진행해서 모든 depth를 담고 max value를 print했다. 끝~ #include #include #include #include #include #include using namespace std; int N, M; string map[51]; int visit[51][51] = { 0 }; int temp[51][51] = { 0 }; vector findMax; int dx[] = { 1,0,0,-1 }; int dy[] = { 0,1,-1,0 }; void bfs(int x, int y) { int out; queue q; q.push(make_pair(make_pair(x, y), 0)); while (!q.empty()) { i..
[백준/C++] 2636번: 치즈 로봇청소기도 어려웠는데 이 문제도 어려웠다. 초등부문제라니 정말..^^ 풀이과정을 머릿속으로 떠올려보니, 1) while문을 돌리는데 종료조건은 2) initial함수: visit배열은 사이클을 돌 때마다 초기화해줘야 한다. 3) outAir함수: 외부공기와 내부공기를 구분해줘야 하는데 이는 dfs를 0,0칸에서 돌려주면 자동으로 구분된다. 그 이유는 치즈에 맞닿아있으면 dfs가 탐색을 못하기 때문에 자동으로 못들어간다. 외부공기를 새로운 visit배열에 표시를 해주었다. 4) melt함수: 모든 위치를 돌며 그 위치의 동서남북에서 visit배열의 표시가 하나라도 있으면 외부공기와 맞닿은 부분이 된다. 그래서 이부분을 녹이고, 기존 치즈 갯수에서 1을 빼준다. 5) 출력 만들기: 시간같은 경우 while..
[백준/C++] 9205번: 맥주 마시면서 걸어가기 맥주 마시면서 걸어가는게 참 힘든 일이라는 것을 깨닫게 된 날이다.. 이문제 뭔데 어렵냐ㅠㅠㅠ이해하는데 너무 오래걸려서 자괴감이 들지만 모르는 걸 하나 알게 되었다는 것에 감사하도록 하자. 이 문제의 경우 그래프가 주어지지 않았다. 그래서 직접 그래프를 만들어야 하는데 어떻게 만들어야 할 지 감이 잘 안왔다. 노드의 배열에 이런식으로 간선을 추가해본 적이 없어서 더 어려웠다. 결론적으로 정석풀이들을 참고하여서 코드를 완성했고 따라 쓰면서 이해한 정도다. 1) 메모리초기화 2) pair자료형의 벡터로 집 , n개의 편의점, 페스티벌 이렇게 n+2개를 입력으로 받는다. 3) 그래프를 생성한다. - 현재 노드로 부터 앞으로 갈 수 있는 노드에 대해서 모두 버틸 수 있는 거리라면 연결된 노드로 추가한다. - 여..
[백준/C++] 5014번: 스타트링크 비교적 쉬운 문제이다. 최단경로!!!! 이기 때문에 고민없이 BFS로 풀이를 시작했다. 1) 이 문제는 1차원 bfs문제이다. 2) bfs의 종료조건은 원하는 층에 도달했을 때 3) queue에 담는 조건은 최저층~최고층사이 이면서 방문한 적이 없는 애들 #include #include using namespace std; int F, S, G, U, D; int dx[] = {0, 0}; int visit[1000001]; void bfs(int x, int d) { queue q; visit[x] = 1; q.push(make_pair(x, d)); while (!q.empty()) { int cx = q.front().first; int depth = q.front().second; q.pop();..
[백준/C++] 2468번: 안전영역 까다롭지 않은 문제였다. 나도 쉬우니 다들 잘 풀듯,,, 핵심은 비가 아예 안올지도 모른다는 것을 주의해야 한다는 점. 나도 첫제출때 이거땜시 틀렸다. 글고 문제도 약간 이해가 잘 안됐는데 그냥 비오는 높이를 1씩 늘려가면서 연결된 뭉탱이 갯수만 세면 된다. 비 온 높이를 계속 올리다가 4가 되었을 때 map: 비 온 높이를 계속 올리다가 6이 되었을 때 map: 반례는 하나만 보면 되는데 3 3 1 1 1 1 1 1 1 1 1 답: 1 풀이는 아래와 같이 했음 1) 비오는 높이가 0부터 제일높은 건물의 높이까지이다. 2) 높이를 0~최대높이까지 while문으로 돌렸다. 3) while문 내부에서 현재 높이에 대한 - DFS를 돌려서 뭉탱이의 갯수를 찾는다. - 걔를 vector에 push한다. 4) 모..
[백준/C++] 2573번: 빙산 (지저분쓰한 DFS풀이) 쉬워보여서 금방 풀 줄 알았으나 나는 난독증에 걸려있었다... 빙하가 녹을 때 1년이 지나면 1씩 녹는 줄 알았는데 알고보니 주변에 빙하가 아닌 부분이 있는 만큼 녹는 것이었다. 그래서 좀 오래걸렸고 좀 지저분하게 푼 것 같다.. (반례모음) https://www.acmicpc.net/board/view/19033 입력 빙산: 1년 지난 빙산: 2년 지난 빙산: 내가 풀었던 과정을 설명해보면, 1) while문 내부에서 2) 방문했는지 확인하는 visit배열과 몇개의 빙하의 높이를 얼마 빼야되는지 계산하는 cnt_0배열을 초기화 3) 종료조건1: 만약 얼음이 없다면 0을 출력하고 break 4) dfs함수를 통해 전체를 돌려서 몇덩이인지 센다. 5) 종료조건2: 만약 1덩이보다 많다면 년수 출력하고 br..
[백준/C++] 7579번: 토마토 토마토가 모두 익는 최단시간을 계산하는 문제이다. 최소비용 문제이고, 간선의 가중치가 1이고 정점과 간선의 개수가 적으면 BFS로 푸는 문제라고 한다... input 순서를 바꾸면 틀리는데 이유를 모르겠다.... (반례모음) www.acmicpc.net/board/view/43699 #include #include using namespace std; int ans; int M, N, H; int map[101][101][101]; int noToma; queue q; int dx[] = { 1, 0, 0, -1, 0, 0, }; int dy[] = { 0, 1, 0, 0, -1, 0, }; int dz[] = { 0, 0, 1, 0, 0, -1 }; bool allRipe(void) { for (int..

티스토리툴바