판교의 메타몽

문제 링크 : https://www.acmicpc.net/problem/1963 1963번: 소수 경로 소수를 유난히도 좋아하는 창영이는 게임 아이디 비밀번호를 4자리 ‘소수’로 정해놓았다. 어느 날 창영이는 친한 친구와 대화를 나누었는데: “이제 슬슬 비번 바꿀 때도 됐잖아” “응 지금 www.acmicpc.net 문제 풀이는 다음과 같다. 1. 필요한 변수들을 선언하고 에라토스테네스의 채로 소수를 구분한다. cin >> n; separate_prime(); // 에라토스테네스의 체 while(n--){ int from,to,ans; cin >> from >> to; ans = bfs(from,to); if(ans==-1) cout

문제 링크 : https://www.acmicpc.net/problem/6087 6087번: 레이저 통신 크기가 1×1인 정사각형으로 나누어진 W×H 크기의 지도가 있다. 지도의 각 칸은 빈 칸이거나 벽이며, 두 칸은 'C'로 표시되어 있는 칸이다. 'C'로 표시되어 있는 두 칸을 레이저로 통신하기 위해서 www.acmicpc.net 이 문제는 유의 사항이 다음과 같다. (1) 통신이 가능한 케이스만 주어진다. (2) 최단 거리가 아닌, 최소로 거울을 활용하는 횟수를 구해야한다. (3) 거울을 사용한다는 뜻은 방향을 바꾼다는 의미이다 문제 풀이는 다음과 같다. 1. 필요한 변수들을 선언하고 값을 입력 받는다. 코드는 하기와 같으며, 설명은 아래를 참고하자. void input() { int temp = ..

문제 링크 : https://www.acmicpc.net/problem/16973 16973번: 직사각형 탈출 크기가 N×M인 격자판에 크기가 H×W인 직사각형이 놓여 있다. 격자판은 크기가 1×1인 칸으로 나누어져 있다. 격자판의 가장 왼쪽 위 칸은 (1, 1), 가장 오른쪽 아래 칸은 (N, M)이다. 직사각형의 가장 www.acmicpc.net 처음 문제를 접근했을때, Brute Force마냥 시간초과를 피하기 위해 갈 수 없는 영역들은 모조리 방문표시를 했다. BFS와 Brute Force의 조합으로 어찌저찌해서 정답은 맞췄지만, 시간효율성이 좋지 못하다는 것을 깨닫고 다른 방법을 고안하게 되었다. 그러다 터득한 방안은 다음과 같은데, 우선 가장 첫 번째로 주어지는 사각형의 시작 넓이에는 1이 없..

문제 링크 : https://www.acmicpc.net/problem/16236 삼성 SW 코딩테스트에 출제됐던 문제다. 문제 풀이를 따지기 전에, 먼저 굵직한 로직은 다음과 같다. (1) 현재 상어의 위치를 전역 변수로 저장하고, 상어의 위치에 있던 '9'는 '0'으로 변경한다. (2) while문을 세워서 상어가 물고기를 한 마리라도 먹을 수 없을때까지 while문의 roop를 진행한다. (2)-(2) 이때 while문 내부에 bool문형 bfs함수를 세운다. bfs함수는 먹을 수 있는 물고기가 있으면 true를 반환하고, 아니면 false를 반환한다. (3) 모든 while문을 최종적으로 빠져나오면 정답을 출력한다. 문제 풀이는 다음과 같다. 1. 먼저 전역으로 선언한 변수들은 다음과 같다. in..

문제 링크 : https://www.acmicpc.net/problem/16954 16954번: 움직이는 미로 탈출 욱제는 학교 숙제로 크기가 8×8인 체스판에서 탈출하는 게임을 만들었다. 체스판의 모든 칸은 빈 칸 또는 벽 중 하나이다. 욱제의 캐릭터는 가장 왼쪽 아랫 칸에 있고, 이 캐릭터는 가장 오른쪽 www.acmicpc.net 이 문제에서 굳이 벽의 위치를 1초마다 변환시키지 않아도, 이미 최초에 저장된 벽의 위치로 탈출 여부를 판단할 수 있다는 것이 키 포인트이다. 문제 풀이는 다음과 같다. 1. 필요한 변수들을 선언하고 값을 입력받는다. 이 문제는 애초에 8*8 행렬로 고정되어 시작되므로, 동적할당을 하지 않고 전역 변수로 선언해도 메모리를 낭비할 일이 없다. int y,x,m,ny,nx,m..

문제 링크 : https://www.acmicpc.net/problem/16933 16933번: 벽 부수고 이동하기 3 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000), K(1 ≤ K ≤ 10)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다. (1, 1)과 (N, M)은 항상 0이라고 가정하자. www.acmicpc.net 이미 풀어봤던 문제이지만, 더 효율적인 방법이 있기에 한 번 더 해설을 작성한다. 백준 16933번 벽 부수고 이동하기 3 - tuple (C++) 문제 링크 : https://www.acmicpc.net/problem/16933 16933번: 벽 부수고 이동하기 3 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000), K(1..

문제 링크 : https://www.acmicpc.net/problem/16933 16933번: 벽 부수고 이동하기 3 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000), K(1 ≤ K ≤ 10)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다. (1, 1)과 (N, M)은 항상 0이라고 가정하자. www.acmicpc.net 이 문제는 백준 14442번 벽 부수고 이동하기 2의 상위호환 버젼이다. 백준 14442번 벽 부수고 이동하기 2 (C++) 문제 링크 : https://www.acmicpc.net/problem/14442 14442번: 벽 부수고 이동하기 2 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000), K(1 ≤ K ≤ 10)이 주..

문제 링크 : https://www.acmicpc.net/problem/14442 14442번: 벽 부수고 이동하기 2 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000), K(1 ≤ K ≤ 10)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다. (1, 1)과 (N, M)은 항상 0이라고 가정하자. www.acmicpc.net 문제 풀이는 다음과 같다. 1. 먼저 필요한 배열과 변수들을 선언해주고 값을 입력 받는다. 배열의 값은 char 타입으로 주어지므로, 원한다면 char 타입의 배열을 선언해도 되지만 나는 편의상 int형 배열에 값을 저장했다. int n, m, k, y, x, ny, nx, my[] = { 1,0,-1,0 }, mx[] = { 0,1,0,-1 },..

문제 링크 : https://www.acmicpc.net/problem/16946 16946번: 벽 부수고 이동하기 4 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 한 칸에서 다른 칸으로 이동하려면, 두 칸이 인접해야 한다. 두 칸이 www.acmicpc.net 이 문제는 다음과 같은 방법으로 접근할 경우 시간초과를 겪게된다. 배열의 값이 1인 경우, 해당 위치를 기준으로 4방위의 값이 0인 곳에서 DFS / BFS를 진행해 이동할 수 있는 칸의 갯수를 센다. 시간 제한은 2초인데, 1000*1000배열을 하나하나 BFS / DFS로 파고들었다가는 시간초과가 날 수 밖에 없다. 때문에 이 문제는 좀더 거시적인 관점에서 ..

문제 링크 : https://www.acmicpc.net/problem/12886 12886번: 돌 그룹 오늘 강호는 돌을 이용해 재미있는 게임을 하려고 한다. 먼저, 돌 세개는 그룹으로 나누어져 있으며 각각의 그룹에는 돌이 A, B, C개가 있다. 강호는 모든 그룹에 있는 돌의 개수를 같게 만들려고 www.acmicpc.net 이 문제에서 핵심 요소는 이미 거쳐갔었던 돌의 갯수들을 어떻게 skip하느냐이다. 즉, 방문했던 곳은 재방문하지 않는다는 BFS와 DFS의 기본 사항을 어떻게 지키느냐가 관건인데, 나는 다음과 같은 방법을 사용했다. 돌 그룹 3개중 갯수를 바꿀 수 있는 그룹은 2개 뿐이다. 때문에 2개의 돌 그룹의 갯수들을 문제의 요구대로 먼저 갯수를 변경해준 뒤, 만약 변경된 갯수들이 이미 거..