문제 링크 미로 탈출 풀이 BFS를 이용하는 문제 미로를 만들면서 출발 지점인 stt와 도착 지점인 end를 만들어준다. BFS를 돌리는데 시간이 갱신될 time을 3차원 배열로 만들어준다. 원래 2차원 배열의 BFS는 방문한 지점을 다시 방문하지 않는데, 이 문제는 레버를 누르고 도착 지점으로 가야하기 때문에 왔던 길을 다시 방문할 수도 있다. 구조체 Cell을 정의한다. 위치가 담길 y와 x, 레버가 당겨졌었는지 확인할 flag로 구성되어 있다. 도착지점부터 q에 넣고 상하좌우를 탐색한다. 범위 밖이거나 벽이거나 방문 했었다면 continue, 레버라면 해당 지점에서 차원이 옮겨지게 된다. time을 갱신하고 q에 새로운 위치를 넣어준다. time[end.first][end.second][1]을 re..
문제 링크 아이템 줍기 풀이 BFS문제인데, 좌표를 두 배 확대하는 아이디어로 풀 수 있는 문제 2배하게 되면 각 영역의 점과 점을 잇는 선을 따로 구할 수 있어 겹치는 문제를 해결할 수 있다. 각 좌표는 50이하로 들어오므로 배열은 원래 51 사이즈로 만들어야하는데, 두 배이기 때문에 102 크기로 만든다. 사각형을 돌면서 각 좌표는 두 배해주고 1로 영역을 만들어준다. 좌표의 시작+1부터 끝-1까지는 안쪽이기 때문에 0으로 만든다. 외곽선을 BFS로 탐색하면서 거리를 구해주고, 답은 /2해줘야 나온다. 코드 #include #include #include #include using namespace std; int dy[4] = {-1,0,1,0}; int dx[4] = {0,1,0,-1}; int ..
문제 링크 14940번: 쉬운 최단거리 풀이 BFS를 이용하는 문제. 반례를 잘못 처리해서 틀렸었음 3 3 2 0 0 0 0 1 0 1 1 입력을 받으며 목표지점일 경우(2일 경우)에는 dest에 넣어준다. BFS를 시작한다. 각 거리가 갱신될 벡터 dist는 -1로 초기화한다. 보통 난 0으로 초기화해주는데, 여기서 갈 수 있는 길인데 못 가는 경우를 처리하기 위해 -1로 처리한다. 상하좌우를 돌면서 범위 밖이거나 0이라면 continue한다. 각 거리를 갱신해준 뒤 q에 push한다. dist를 출력하는데, 반례와 같이 원래 못 가는 곳은 0으로 처리해야 하는데, -1로 출력될 수 있어 여기서 처리해준다. arr[i][j]가 0인데 dist[i][j]가 0이 아니라면 0으로 만들어준 뒤 출력한다. 코..
문제 링크 1238번: 파티 풀이 인접 리스트들에 대해 각 정점에서 목표 정점까지의 최단 거리를 구하는 다익스트라 문제 우선 순위 큐로 풀어야하나 싶은데 큐로 해도 풀리긴 함 값을 입력 받으며 인접 리스트를 만들어줌 func에서 현재 정점인 cur에서 각 노드까지의 최단 거리를 구해준다. 거리를 갱신해줄 dist를 무한대로 만들어주고 시작 노드는 0 큐가 빌 때까지 반복하는데, 현재 노드인 curN에서 연결된 정점을 보며 각 노드까지 거리가 최소로 갱신될 때만 dist 갱신과 q에 추가해준다. 그렇게 현재 정점에서 각 노드까지의 최소 거리가 구해진다. xdist는 집으로 각자 돌아갈 때인데, 한 번만 구해주면 각 노드까지의 최소 거리가 만들어진다. xdist[i]와 cdist[i]를 더한 값이 가장 큰 ..
문제 링크 1138번: 한 줄로 서기 풀이 answer 벡터를 0으로 초기화한다. 작은 키부터 자리를 찾아가는데, 이렇게 하게 되면 answer의 0은 자기보다 큰 키가 될 것이다.(자기 이후에 찾게 될테니) answer를 돌면서 자기보다 큰 키면(answer[j] == 0) zeroCnt를 하나 더해준다. 그렇게 zeroCnt가 arr[i]와 같아지게 되면 해당 자리의 다음 자리에 넣어주면 된다. 그 자리가 비어있지 않다면(0이 아니라면) 빈 자리를 찾아 넣어준다. answer를 출력한다. 코드 #include #include using namespace std; int main() { ios_base::sync_with_stdio(0); cin.tie(0); int n; cin >> n; vector..
문제 링크 16507번: 어두운 건 무서워 풀이 누적합 문제 사진의 밝기를 입력받으며, 각 행마다 누적합을 구한다. func를 통해 영역의 사진 밝기 평균을 구하는데, 각 행열은 1부터 시작하므로 -1 해준다. r1부터 r2까지 행마다 c2에서 c1-1의 값을 빼주면 해당 행의 영역 값을 구할 수 있다. c1이 0이라면 c1-1에서 에러가 나니까 예외 처리를 해준다. 사각형의 영역값으로 sum을 나눠주면 된다. 코드 #include #include using namespace std; int func(vector &arr, int r1, int c1, int r2, int c2) { int sum = 0; for (int i = r1; i > r >> c >> q; vector arr(r, vector(..
문제 링크 6588번: 골드바흐의 추측 풀이 소수 문제인데 시간 초과로 꽤나 머리 아팠던 문제 먼저 최대 숫자인 1000000까지 소수를 체크하기 위한 배열을 정의한다. 소수가 아닐 경우 true이다. 에라토스테네스의 체를 통해 소수인지 체크한다. 첫번째 반목문에서 1000000의 제곱근까지만 구해도 내부 반목문에서 해당 숫자의 제곱부터 배수를 체크할 것이다. sosu[i]가 true라면 소수가 아닌 것으로 이미 체크가 된 것이므로 continue 2번이 해당되지 않으면 해당 숫자는 소수이고, 그 소수의 제곱부터 배수들을 소수가 아닌 것으로 체크한다. 왜 배수를 체크하는데 제곱부터 구하냐면, 해당 수보다 작은 숫자의 배수는 그 전 숫자들에서 구했을 것이므로 중복된다. 예를 들어 j가 5라면 배수인 2부터..
문제 링크 15903번: 카드 합체 놀이 풀이 처음엔 백트래킹인가 했는데, 어차피 중복으로 카드를 뽑아도 되고 최소 숫자를 구하는 것이기 때문에 정렬해서 풀면 되는 것이라 판단했다. 중간에 캐싱할 때 형을 잘못 넣어서 틀렸는데 바꿔주니 바로 성공 생각해보니 우선순위 큐로 풀어도 되는 문제 m번 뽑을 때까지 계속해서 배열을 오름차순 정렬하고 제일 밑에 있는 두개를 뽑아 더해서 적용한다. cards를 돌면서 answer 갱신 후 출력한다. 코드 #include #include #include using namespace std; int main() { ios_base::sync_with_stdio(0); cin.tie(0); int n, m; cin >> n >> m; vector cards(n); for ..
문제 링크 2529번: 부등호 풀이 백트래킹 문제 0부터 9까지 숫자 한 번만 사용이 가능하므로 bool 배열을 통해 체크한다. func함수는 숫자가 만들어질 때까지 재귀호출을 한다. num은 이전 숫자, idx는 현재 부등호, curString은 현재까지 만든 숫자, sign은 부등호의 vector, used는 사용한 숫자 체크를 위한 배열이다. used의 각 인덱스가 해당 숫자의 사용 여부이다. idx가 sign의 size와 같다면 숫자가 잘 만들어진 것이므로 minAnswer와 maxAnswer를 갱신한 뒤 return한다. 0부터 9까지 반복문을 돌며, 사용한 숫자가 아니고, 해당 숫자(i)와 이전 숫자 num과 부등호 관계가 성립한다면 재귀 호출한다. 이 때, used도 체크해준 뒤 재귀로 넘기..
문제 링크 1240번: 노드사이의 거리 풀이 BFS를 이용하는 문제 먼저 노드와 거리를 입력 받아 인접 리스트를 만든다. 거리를 알고 싶은 노드 쌍 stt, end의 입력을 받으면서 BFS함수를 실행한다. dist 벡터는 stt 노드에서 각 인덱스 노드까지의 거리를 저장하는 벡터로 -1로 초기화한다. stt 인덱스는 0으로 초기화 한 뒤, queue를 이용해 너비 탐색을 시작한다. 현재 노드인 cnode와 연결된 노드들을 반복문으로 탐색하며 다음 노드들을 q에 넣고, 거리가 처음 갱신 되는 노드들은 dist[tnode]=dist[cnode]+twei로 갱신한다. dist[end]를 출력한다. 코드 #include #include #include using namespace std; int BFS(int ..
