너와 나의 스토리

문제: www.acmicpc.net/problem/16954 8×8인 체스판에서 탈출하는 게임 체스판의 모든 칸은 빈칸(.) 또는 벽(#) 중 하나이다. 욱제의 캐릭터는 가장 왼쪽 아랫 칸에 있고, 이 캐릭터는 가장 오른쪽 윗 칸으로 이동해야 한다. 이 게임의 특징은 벽이 움직인다는 점이다. 1초마다 모든 벽이 아래에 있는 행으로 한 칸씩 내려가고, 가장 아래에 있어서 아래에 행이 없다면 벽이 사라지게 된다. 욱제의 캐릭터는 1초에 인접한 한 칸 또는 대각선 방향으로 인접한 한 칸으로 이동하거나, 현재 위치에 서 있을 수 있다. 이동할 때는 빈 칸으로만 이동할 수 있다. 1초 동안 욱제의 캐릭터가 먼저 이동하고, 그 다음 벽이 이동한다. 벽이 캐릭터가 있는 칸으로 이동하면 더 이상 캐릭터는 이동할 수 없..

문제: www.acmicpc.net/problem/16137 두 번 연속으로 오작교를 건너지는 않기 2 이상의 수는 모두 오작교임을 명심하자 절벽을 정확히 하나 골라 주기가 M분인 오작교를 하나 더 놓아 줌 절벽이 가로와 세로로 교차하는 곳에 오작교를 놓을 수 없다. 문제 풀이: bfs를 이용해 문제를 해결하였다. 오작교의 주기인 M이 20 이하이기 때문에, 건널 수 있는 시간이 되지 않았다면 그 자리에서 기다리도록 하였다. visit 체크는 현재 위치(x, y)와 오작교를 설치 여부를 고려하였다. 이 문제의 핵심은 조건을 잘 이해하는 것!! 소스 코드: #include #include #include #include #include #include using namespace std; int n, m,..

문제: www.acmicpc.net/problem/17244 첫 번째 줄에는 집의 가로 길이 N과 세로 길이 M이 입력된다. (3 ≤ N, M ≤ 50) "가로가 N"인 것을 주의하자! 두 번째 줄부터는 집의 구조가 예제 입력과 같이 주어진다. 비어있는 곳은 '.'로 벽은 '#'로 입력된다. 경재 씨의 현재 위치는 S, 나가는 문의 위치는 E, 챙겨야 하는 물건은 종류에 상관없이 X로 입력된다. 챙겨야 하는 물건은 최대 5개까지 있을 수 있다. 집은 언제나 벽으로 둘러싸여 있고, 나가는 문은 언제나 하나이다. 문제 풀이: bfs로 문제를 해결했다. queue에 들어갈 데이터는 다음과 같다. 현재 위치 (x, y) 값 지금까지 습득한 아이템 정보 각 아이템들을 map을 이용해 넘버링해준다. item 번호 ..

문제: https://swexpertacademy.com/main/solvingProblem/solvingProblem.do SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 소스코드: #include #include #include #include #include #include using namespace std; int tc, n,mi, dist[51][51], arr[51][51],res; typedef pair P; int dx[4] = { -1,0,1,0 }; int dy[4] = { 0,1,0,-1 }; vector adj; queue q; int dfs(int curx,int cury) { if (..

문제: https://www.acmicpc.net/problem/1938 문제 풀이: 통나무의 길이는 항상 3이다. 그리고 중심을 기준으로 회전한다. -> 통나무의 이동, 방문 여부, 거리 계산은 [중심점]과 [가로/세로] 기록하면 된다. 만약 통나무가 세로인 상태라면 ↓: X축 → : Y축 (X-1,Y) (X,Y) (X+1,Y) 통나무를 회전시키려면, 중심점을 중심으로 두고 주변 3x3 영역에 아무것도 없어야한다. 소스 코드: #include #include #include #include #include #include #include #include #include #include #define inf 987654321 using namespace std; typedef pair P; int n,d..

문제: https://www.acmicpc.net/problem/13565 문제 풀이: 맨 윗줄에서 0인 위치를 큐에 넣어놓고 시작해서 마지막 줄에 도달하는지만 보면 된다. 소스 코드: #include #include #include #include #include using namespace std; typedef pair P; int n, m; int dx[4] = { 0,0,1,-1 }; int dy[4] = { 1, -1, 0, 0 }; char arr[1002][1002]; bool visit[1002][1002]; int main() { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin >> n >> m; for (int i = ..

문제: https://www.acmicpc.net/problem/3830 문제 풀이: 1. 입력 받은 샘플에 상대적인 무게를 지정해준다. (그룹별로) 2. 두 그룹이 합쳐지는 경우 사이즈가 작은 그룹을 큰 그룹에 포함되도록 만든다 큰 그룹의 끝에서 작은 그룹으로 dfs를 돌려서 큰 그룹의 번호와 큰 그룹의 상대적인 무게에 맞는 무게를 부여 이미 존재하는 그룹에 새로 연결하는 경우는 그냥 상수시간으로 해결 가능하고, 두 그룹 묶을 때, 작은 그룹만 dfs 돌리니까 최악의 연산은 전체 dfs 한 번 돌리는 정도가 된다. * 주의: 무게 저장할 때, long long 써야하는데, 이것만 long long으로 하는 것이 아니라 이 것과 관련된 변수들도 다 long long으로 해줘야 한다. 소스 코드: type..

문제: https://www.acmicpc.net/problem/12763 문제 풀이: dfs로 풀었다 dist[n]에 pair로 시간이랑 금액 저장 현재 가는 정점이 원래 저장된 값(다른 루트로 온 결과 값)보다 시간이랑 금액 둘 다 손해면 안 가고 둘 중 하나라도 이득이면 감 만약 제한된 금액이나 시간이 이미 지나게 되면 안감 소스 코드: typedef pair P; int n,m, time, money,res; vector dist; vector adj; void dfs(int cur) { if (cur == n) { res = min(res, dist[cur].second); return; } for (auto &i : adj[cur]) { if (dist[i.first].first money) ..