본문 바로가기

Problem/DFS

[백준알고리즘] 12094번 2048(HARD) https://www.acmicpc.net/problem/12094 나에게 똥을 준 문제.. ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ 거의 정신 놓고 풀었음... 하도하도 안되서 다른 분들 것을 참고하였다... 정답 비율에 일조한 나의 채점 현황^^* 워매 힘든거.. dfs를 이용하여 완전탐색으로 특정 조건이 되었을 때 최대값을 찾는 문제이다!2048(EASY)와는 다르게 2048(HARD)는 count가 10까지 가야하기 때문에 수행시간을 줄이는 것이 핵심이 되는 문제이다!! 첫 번째로, 모든 count 마다의 board에 대한 visited 배열을 만들어서 저장된 최댓값보다 현재가 작은 값인 경우 가지 않는 것으로 구현하려 했다.ex) 4번 이동해서 1024가 나온 것이 저장된 최대값인데, 지금 4번 이동해서 512..
[백준알고리즘] 12100번 2048(EASY) https://www.acmicpc.net/problem/12100 으아ㅏㅏ 하다가 도저히 안되어서 다른 분들 것을 참고하였다..2차원 배열 인자로 넘기고 값 받고 할 때 계속 값이 아니라 주소를 받아와서 애꿎은 값이 변해버리는데 2차원 배열 값 인자로 주고 받는 것을 명확히 이해하고 정리해야겠다.. ㅠㅠ 같은 숫자일 때 그 방향 처음것부터 두개까지만 합치고 다음 index로 넘어가는 것을 구현할 때 실수가 있었는지 내가 했을 때 값이 제대로 나오지 않았다.. 코드도 이상하고 ㅠㅠ 그래서 다른 사람들은 어떤 방식으로 구현하는지 찾아보았는데 굉장히 여러 가지 방법이 있었다. 그 중에 나는 queue를 이용해서 이동해야 하는 곳의 값을 담아둔 후 빼면서 합쳐 갱신하는 방법을 이용해 풀었다! 전체적인 틀은 d..
[백준알고리즘] 6603번 로또 https://www.acmicpc.net/problem/6603 로또 성공한국어 시간 제한메모리 제한제출정답맞은 사람정답 비율1 초128 MB93215049357454.507%문제독일 로또는 {1, 2, ..., 49}에서 수 6개를 고른다.로또 번호를 선택하는데 사용되는 가장 유명한 전략은 49가지 수 중 k(k>6)개의 수를 골라 집합 S를 만든 다음 그 수만 가지고 번호를 선택하는 것이다.예를 들어, k=8, S={1,2,3,5,8,13,21,34}인 경우 이 집합 S에서 수를 고를 수 있는 경우의 수는 총 28가지이다. ([1,2,3,5,8,13], [1,2,3,5,8,21], [1,2,3,5,8,34], [1,2,3,5,13,21], ..., [3,5,8,13,21,34])집합 S와 k가 주어..
[백준알고리즘] 2583번 영역 구하기 https://www.acmicpc.net/problem/2583 좌표로 배열의 영역 표시하는 방법 ex) 0 2 4 4 일 때, (1,0) (1,1) (1,2) (1,3) (2,0) (2,1) (2,2) (2,3) for(i = 1; i for(i = M-4; i for(j = 0; j < 4; j++) 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081#include#include#incl..
[백준알고리즘] 4963번 섬의 개수 https://www.acmicpc.net/problem/4963 가로, 세로 원래 잘 안보는데 진짜 잘 봐야한다는 걸 ㅠㅠㅠ 문제풀면서 깨달으면서도 안봄 ㅠㅠㅎ그흑 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263#include#includeusing namespace std; int w; int h;int map[51][51];int visited[51][51]; int dx[8] = { 0,0,1,-1,-1,-1,1,1};int dy[8] = { 1,-1,0,0,-1,1,-1,1 }; void howmanylands(int _i,int _j..
[백준알고리즘] 2636번 치즈 https://www.acmicpc.net/problem/2636 치즈 성공시간 제한메모리 제한제출정답맞은 사람정답 비율1 초128 MB32471479113550.602%문제아래 과 같이 정사각형 칸들로 이루어진 사각형 모양의 판이 있고, 그 위에 얇은 치즈(회색 으로 표시된 부분)가 놓여 있다. 판의 가장자리(에서 네모칸에 엑스친 부분)에는 치즈가 놓여 있지 않으며 치즈에는 하나 이상의 구멍이 있을 수 있다.이 치즈를 공기 중에 놓으면 녹게 되는데 공기와 접촉된 칸은 한 시간이 지나면 녹아 없어진다. 치즈의 구멍 속에는 공기가 없지만 구멍을 둘러싼 치즈가 녹아서 구멍이 열리면 구멍 속으로 공기가 들어 가게 된다. 의 경우, 치즈의 구멍을 둘러싼 치즈는 녹지 않고 ‘c’로 표시된 부분만 한 시간 후 에 ..
[백준알고리즘] 2606번 바이러스 https://www.acmicpc.net/problem/2606 바이러스 성공시간 제한메모리 제한제출정답맞은 사람정답 비율1 초128 MB220269040634040.000%문제신종 바이러스인 웜 바이러스는 네트워크를 통해 전파된다. 한 컴퓨터가 웜 바이러스에 걸리면 그 컴퓨터와 네트워크 상에서 연결되어 있는 모든 컴퓨터는 웜 바이러스에 걸리게 된다.예를 들어 7대의 컴퓨터가 과 같이 네트워크 상에서 연결되어 있다고 하자. 1번 컴퓨터가 웜 바이러스에 걸리면 웜 바이러스는 2번과 5번 컴퓨터를 거쳐 3번과 6번 컴퓨터까지 전파되어 2, 3, 5, 6 네 대의 컴퓨터는 웜 바이러스에 걸리게 된다. 하지만 4번과 7번 컴퓨터는 1번 컴퓨터와 네트워크상에서 연결되어 있지 않기 때문에 영향을 받지 않는다.어느..
[백준알고리즘] 2667번 단지번호붙이기 https://www.acmicpc.net/problem/2667 이런것도 한번에 못 푸는 나는 진짜똥멍청이인가부다.... 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667#define _CRT_SECURE_NO_WARNINGS#include#include#include#include#includeusing namespace std; int N = 0;int cnt = 0;int arr[26][26] = { 0 };int visited[26][26] = { 0 }; int dx[4] = { 0,0,1,-1 };int dy[4] = ..

티스토리툴바