BFS4 [백준] 16166번 서울의 지하철 (C++) https://www.acmicpc.net/problem/16166 단순한 bfs문제라 생각하였는데 생각보다 풀고나니 어느정도 구현이 들어가있는 문제라고 생각하였다. 틀렸습니다를 여러번 받았던 문제였다 이유는 방문체크를 1호선의 0번째 요소 이런식으로 방문체크를 하였던지라몇번 역의 방문체크때문에 계속 틀렸습니다를 받았고 다른사람한테 이 문제를 공유했는데 약간 다르게 0-1 bfs로 풀릴 수 있는 문제였다고 한다 지금 생각해보면 그냥 1차원배열을 사용해서몇호선에 대한건지만 방문체크해주면 쉽게 풀렸을거같은 문제였다. 코드#include using namespace std;typedef pair pii;typedef long long ll;#define Endl "\n"#define MAX 1e9int .. 2025. 4. 1. [백준] 16932번 모양 만들기 (C++) https://www.acmicpc.net/problem/16932 문제를 보고 단순하게 접근했을때 0인 좌표 구간에서 1로 만들어 bfs를 통해 탐색 후 1의 개수를 세어최댓값을 갱신하여 출력하는 로직을 생각하고 접근했지만 당연하게도 시간초과가 발생하였다.이후로 어떻게하면 시간초과없이 풀 수 있을까를 생각하다가 1인 구간을 나눠서 더해주면 되겠다는 생각을 하였다. 입력 받은 2차원 배열을 바탕으로 1인 구간을 탐색 후 배열에 해당 구간에 대한 1의 개수를 넣어준다.이후에 0을 탐색하여 상하좌우에 대해 0이 아닌 다른 값이 있을 경우 그 값을 대입한다이때 빨간색 동그라미인 0처럼 2가 중복으로 들어가면 안되기때문에 set을 사용하여 중복을 없애줘 계속해서 최댓값을 갱신한다. 마지막에 0인좌표 1을 더.. 2025. 3. 23. [백준] 22352번 항체 인식 (C++) https://www.acmicpc.net/problem/22352 문제를 보고 풀이를 40분정도 한 것 같다 생각한것 보다 조금 더 복잡한 문제였다.먼저 백신을 놓기 위해서 N, M배열을 모두 순회하며 bfs함수를 돌았다.이후 처음 시작했던 원소와 인접한 모든 곳들을 방문체크를 한 후 방문하지 않았던 요소들을 비교하였다 만약 다를 경우 백신이 아니기 때문에 NO를 출력주는 방식으로 풀이를 진행하였다. // baekjoon 17835#include using namespace std;typedef pair pii;typedef long long ll;#define endl "\n"#define INF int(1e9)int dx[9] = {-1, 1, 0, 0, -1, -1, 1, 1, 0};int .. 2025. 3. 2. [백준] 23352번 방탈출(C++) https://www.acmicpc.net/problem/23352 문제에서 요구하는 조건이 2가지가 있다1. 임의의 방에서 다른 방으로 이동할 때는 항상 두 방 사이의 최단 경로로 이동한다.2. 1번을 만족하는 경로 중 가장 긴 경로의 시작 방과 끝 방에 적힌 숫자의 합 1번 조건이 의미하는 바는 1에서 출발할 경우 7까지 도착하는 최단 경로는 1 -> 2 -> 7이다 즉 1 -> 3 -> 4-> 2 -> 7 이렇게 돌아서 가는 경우가 불가능 하다는 의미이다. 2번 조건이 의미하는 바는 만약 출발점이 6이고 도착점이 7이라고 가정했을때 거리는 3이 될것이고 비밀번호는 13이 되어 비밀번호는 최댓값이 될 것이다.두번째로 출발점이 5이고 도착점이 7이라고 가정했을때 거리는 4이고 비밀번호는 12가 될 것.. 2025. 2. 4. 이전 1 다음
