본문 바로가기

IT/BOJ117

백준(BOJ) 2931 가스관 ** 이 문제를 푸는데 필요한 개념은 BFS와 DFS 인 것 같다. 아이디어는 각 칸에 4개의 방향에 대해서 연결이 되어있으면 1로 저장한다. ex ) +의 경우 -> {1,1,1,1} -의 경우 -> {0,1,0,1} 1의 경우 -> {0,1,1,0} 이 후 bfs를 통해 탐색하는데 1로 되어있음에도 그 다음 칸이 0으로 되어있다면 그 칸이 바로 지워진 칸이 된다. 지워진 칸을 찾은 뒤 그 칸에 4방향에서 연결된 가스관의 위치를 확인하여 정답을 출력해 주면 된다. ...코드가 좀 지저분 한거 같다..#include #include #include #include #include #include #include #include #include #include #include #define MAX 205 #de.. 2018. 6. 1.
백준(BOJ) 1865 웜홀 ** 벨 만 포드 방식을 알고 있다면 쉽게 풀 수 있는 문제이다. 내가 실 수 했던 점은 "만약에 시간이 줄어들면서 출발 위치로 돌아오는 것이 가능" 을 "음수의 값을 가지는 노드가 있으면 가지면 YES"로 이해했다. "모든 웜홀의 정보 S의 노드가 음수의 값을 가지면 YES"가 맞다. #include #include #include #include #include #include #include #include #include #define MAX 40005 #define MOD 1000000007 #pragma warning(disable:4996) using namespace std; int t,n,m,w,a,b,c; int map[505][505],cur[505]; bool tf[505]; vector.. 2018. 6. 1.
백준(BOJ) 11779 최소비용 구하기 2 ** 본인은 다익스트라 알고리즘을 이용해서 풀었다. 1. 현재 노드에서 갈수 있는곳 중 가장 적은 비용인 노드를 선택한다. 2. 노드로 이동 후, 노드에 가는 비용을 업데이트한다. 가장 기본적인 방식으로 푼것 같다. ** : 가장 기본적인 다익스트라 방식이고, 최소비용 뿐 아니라 경로를 저장하는 부분이 추가되었다. #include #include #include #include #include #define MAX 100000001 #pragma warning(disable:4996) using namespace std; int city_n,bus_n,bus[1005][1005],city[2][1005],a,b,c; vector v[1005],current; int getMin(void) { int mi=-1.. 2018. 6. 1.
백준(BOJ) 1261 알고스팟 2 ** 다익스트라 알고리즘을 이용하여 풀었다. 1. 현재 노드에서 갈수 있는곳 중 가장 적은 비용인 노드를 선택한다. 2. 노드로 이동 후, 노드에 가는 비용을 업데이트한다. 배운점 * 128MB이면 배열의 크기는 대략 5000*5000을 넘으면 안된다. * 반례가 모두 성립되었는데도 해결이 되지 않았다면 간단한 실수를 조심하자. #include #include #include #include #include #define MAX 10005 #pragma warning(disable:4996) using namespace std; int ori[105][105], node_n,node[2][20005], x,y; int dy[4] = { 0,-1,0,1 }, dx[4] = { -1,0,1,0 }; char ch.. 2018. 6. 1.

티스토리툴바