김머성 블로그

[BAE/<JOON> 문제풀이] 2178. 미로

https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 말 그대로 미로를 탐색해서 1,1 부터 n, m까지 최단 경로를 찾아내는 문제다. 어제 풀던 섬을 오늘도 못풀어서 1일 1문제는 해야하기 때문에 다른 문제로 때운다.. (ㅠㅠ).. 이 문제도 bfs로 굉장히 단순한데, 내가 그 동안 bfs문제들을 모조리 잘못 풀이하고 있었다는 것을 알았다. 우선 아래 코드를 보자. queue q; q.push({ 1, 1, 1 }); while (!q.empty()) { int x = q.fro..

[BAE/<JOON> 문제풀이] 16000. 섬 (미완)

https://www.acmicpc.net/problem/16000 16000번: 섬 N 개의 줄에 길이 M 의 문자열을 출력하라. 이 중 i 번째 줄의 j 번째 문자는 (i, j) 셀의 상태를 나타내어야 한다. 만약 (i, j) 셀이 바다라면 해당 위치에 '.'을 출력해야 하고, 안전한 섬의 일부라면 해당 위치에 'O'를 출력해야 하고, 위험한 섬의 일부라면 해당 위치에 'X'를 출력해야 한다. www.acmicpc.net 간단한 탐색문제 인줄 알았는데 자꾸 메모리 초과가 뜬다..(심지어 제한이 768메가에 5초임..) 아마도 단순히 BFS탐색만 하는게 아니라 뭔가 추가적인 기법이 필요하거나 함정이 숨어있는 문제 같다. 차라리 문제 자체가 복잡하다면 생각해볼 수 있는 경우가 많아서 여러가지 시도라도 해..

[BAE/<JOON> 문제풀이] 14500. 테트로미노

https://www.acmicpc.net/problem/14500 14500번: 테트로미노 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변끼리 연결되어 있어야 한다. 즉, 꼭짓점과 꼭짓점만 맞닿아 있으면 안 된다. 정사각형 4개를 이어 붙인 폴리오미노는 테트로미노라고 하며, 다음과 같은 5가지가 있다. 아름이는 크기가 N×M인 종이 위에 테트로미노 하나를 놓으려고 한다. 종이는 1×1 크기의 칸으로 나누 www.acmicpc.net 간단한 백트래킹 문제였다. 한가지 다른점은 엿모양 블럭은 한붓그리기가 안되기 때문에 다른 방법을 써야한다는 점이다. (ㄴ 모양이나 ..

[BAE/<JOON> 문제풀이] 16236. 아기상어

https://www.acmicpc.net/problem/16236 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가지고 있고, 이 크기는 자연수이다. 가장 처음에 아기 상어의 크기는 2이고, 아기 상어는 1초에 상하좌우로 인접한 한 칸씩 이동한다. 아기 상어는 자신의 크기보다 큰 물고기가 있는 칸은 지나갈 수 없고, 나머지 칸은 모두 지나갈 수 있다. 아기 상어는 자신의 크 www.acmicpc.net 오랜만에 백준문제를 풀어봤다. 간단한 BFS문제여서 금방 풀 줄 알았는데 한가지 코너 케이스가 있어서 그거 찾고 수정하느라 좀 오래..

[local search/simulated annealing] 완전그래프 탐색

N사이즈의 완전 그래프에서 1번 정점에서 출발한 뒤 모든 정점을 한번만 방문한 뒤 다시 1번 정점으로 돌아오는 경로 중, 가장 비용이 적게드는 경로를 탐색하는 알고리즘을 작성해보자. 단 그래프는 방향 그래프이다. 모든 정점을 방문한 최소값을 찾아야하므로 모든 경로를 완전탐색해야한다. 일반적으로 떠올릴 수 있는 완전탐색 알고리즘을 작성하면 모든 경로를 탐색하기 되므로 1 x (n - 1) x (n - 2) ... 1 x 1의 알고리즘이 완성된다. 즉 알고리즘 복잡도가 n!이 되는 것이다. 10!이 대략 363만 정도니까 정점 10개 넘어가면 거진 못푼다고 봐야한다. 이런 종류의 특별한 해법이 없고 완전 탐색을 해야하는데 주어진 시간 내에 탐색이 불가능한 문제들을 푸는 방법이다. Local Search:: ..

[위상정렬]

위상 정렬이란:: 사이클이 존재하지 않는 방향 그래프에서 간선의 방향을 거스르지 않는 순서로 정점들을 정렬하는 알고리즘을 의미한다. 구현:: 그래프 데이터를 입력 받을 때 각 정점에 대한 진입간선의 수를 별도로 저장해 놓는다. 루프를 돌며 ㄱ. 현재 진입 간선의 수가 0개인 정점을 찾는다. ㄴ. 해당 정점에 연결된 정점들의 진입 간선 수를 1 내리고 해당 정점을 방문 불가 상태로 바꾼다. 위의 과정을 반복하며 정점을 방문 순서대로 찍으면 위상 정렬이 완료된다. for(i=1;i> s; cin >> e; arr[s][++arr[s][0]] = e; enterdg[e]++; 진입간선 카운트 } for(i=1;i