마탁이의 개발 블로그

www.acmicpc.net/problem/9370 9370번: 미확인 도착지 (취익)B100 요원, 요란한 옷차림을 한 서커스 예술가 한 쌍이 한 도시의 거리들을 이동하고 있다. 너의 임무는 그들이 어디로 가고 있는지 알아내는 것이다. 우리가 알아낸 것은 그들이 s지점에서 www.acmicpc.net 최단 거리, 특정한 목적지를 거치는 조건이 있는 ICPC 문제. 1280ms가 나왔는데, 채점 현황을 보니 매우 빠른 코드들이 있어 알고리즘의 차이점 확인 필요. 나같은 경우 Dijkstra 계산을 7번 하고 있는데 이때문에 속도가 매우 느린 듯. 더보기 1280ms #include #include #include #include #include // max size #define TEST_CASE_MAX..

www.acmicpc.net/problem/1504 1504번: 특정한 최단 경로 첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존 www.acmicpc.net 해당 문제는 최단 경로 문제에서 특정한 정점을 무조건 지나야 한다는 조건을 추가한 문제이다. 물론, 특정한 정점을 지나갈 때에도 최단 거리의 경로를 지날 수 있도록 계산해야 한다. 시작점 -> 특정한 점_1 -> 특정한 점_2 -> 도착점의 최단 경로 계산을 나누어야 한다. 시작점 -> 특정한 점_1 특정한 점_1 -> 특정한 점_2 특정한 점_2 -> 도착점 과 시..

www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net 미로를 탐험하면서 벽을 부쉈는지에 대한 상태에 대해 알고 있어야 문제를 풀 수 있었다. 이는 visited[MAX_SIZE+1][MAX_SIZE+1][2] 의 형태로 3차원의 인덱스가 0일경우 부순적 없음, 1일경우 부순적 있음으로 생각하여 BFS 코드를 구현하면 된다. 헤더 파일 중 #include 를 써서 INT_MAX를 사용하고 BFS의 반환 값을 min 값으로 변경하며 사용했다...

www.acmicpc.net/problem/1697 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net BFS를 이용하는 간단한 문제 if() 조건문 안의 메모리 초과 오류를 처음에 생각하지 않고 구현하였다가 디버깅 돌리면서 다시 깨닫게되었음 더보기 #include #include // def #define MAX_SIZE 100000 #define PAIR std::pair #define DEBUG_MODE 0 // global bool visisted[MAX_SIZE + 1]; //..

www.acmicpc.net/problem/7569 7569번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, www.acmicpc.net 7576 문제에서 '층' 이라는 개념이 추가된 것. '층' 이라는 개념만 추가해서 구현해주면된다. 위층, 아래층, 상, 하, 좌, 우를 고려해준다. std 라이브러리를 최대한 사용하지 않고, 배열을 1차원으로만 사용한다면 속도 향상이 된다. 코드 더보기 #include #include #include // struct struct POS { POS() { h = x = y = 0; } P..

www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 미로 탐색을 살짝 응용한 문제 풀면서 주의했던 점은 미로 탐색은 100이 MAX_SIZE 였으나, 이 문제는 1000 이라 vector 사용해서 구성. 또한, 같은 날짜에 모든 '1'의 값을 가진 곳에서 상,하,좌,우 확장이 된다. 176ms 의 시간이 걸렸지만 80ms도 있는 것을 봐선 더 개선할 수 있다. 코드 더보기 #include #include #include // def #define..

www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 미로 탐색의 과정에서 최단 거리를 구하는 문제 -> BFS 인접 행렬을 사용하여 해결을 할려고 하니 메모리 초과가 나온다. (답은 출력됨) 미로의 입력의 경우 배열을 이용[101][101]하여 사용하였고 std::vector와 std::find()를 이용하여 방문여부를 검사하니 메모리 초과는 나오지 않으나 68m의 시간이 걸렸다. 채점현황에서 0ms가 소비되는 코드가 많은 것을 보아 효율을 높일 수 있는 (?) 코드로 수정이 필요하다. 코드 ..

www.acmicpc.net/problem/1012 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net 이전 2667과 유사한 문제라고 생각되어 같은 방식으로 해결. BFS 탐색을 이용해 문제를 해결 코드 더보기 #include #include #include #include // def #define BOARD_MAX_SIZE 50 #define POS_PAIR std::pair // method bool CheckingValid(int x, int y, int X, int Y); void BFS_Search(int map..

www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집들의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. www.acmicpc.net 한국 올림피아드 초등부 문제 역시나 DFS를 초등부 문제에 있다는 것에 신기했지만 정답률도 낮은 것에 신기했음.(다른 분들이 단계별로 풀어보기에 신경안쓰는 것일까.) 풀이 주어진 입력을 인접행렬로 생각해 해결 방문하지 않은 1이 나올때마다 BFS 함수 사용 처음에 결과값을 std::set에 저장해서 정렬 과정의 코드를 생략할려고 했었으나 생각해보니 중복값은 std::set에 저장이 안됨 -> std::vector ..

www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어 www.acmicpc.net 한국정보올림피아드 지역본선 2004 초등부 문제 단계별로 풀어보기 대학교때 코딩 배운 나와 달리 초등부 문제가 DFS 탐색을 이용하는 것은 조금 신기하긴 했다. 풀이 1260 - DFS와 BFS에서 인접행렬을 사용한 DFS를 std::vector를 이용한 인접리스트로 구현하여 탐색하도록 했다. 확실히 속도와 공간 복잡도에 이점은 있다. (문제 난이도가 쉬워 구현도 쉬웠다.) 코드 더보기 #include #includ..