판교의 메타몽

문제 링크 : www.acmicpc.net/problem/13913 13913번: 숨바꼭질 4 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net BFS문제이며, 문제를 대충 읽고 풀었다가는 아래 유의 사항을 놓칠 수 있다. 1. 둘의 위치가 같은 경우 5 5 // n=5, k=5 0 // the number of movement 5 // your accumulated position 2. 위치 출력시 무조건 첫 번째는 출발 지점이 나올 수 밖에 없다. 문제 풀이는 다음과 같다. 1. n과 k를 입력받는다...

문제 링크 : www.acmicpc.net/problem/16197 16197번: 두 동전 N×M 크기의 보드와 4개의 버튼으로 이루어진 게임이 있다. 보드는 1×1크기의 정사각형 칸으로 나누어져 있고, 각각의 칸은 비어있거나, 벽이다. 두 개의 빈 칸에는 동전이 하나씩 놓여져 있고, www.acmicpc.net 문제 풀이는 다음과 같다. 1. 문자형 타입을 입력받을 배열, 2개의 동전의 방문여부를 동시에 확인할 4*4배열(타입은 int,bool 무엇이든 상관없음)을 생성한다. 동전의 위치값 2개 * 동전 2개 이므로, 방문여부는 4개의 값을 한꺼번에 입력받을 수 있어야한다. 2. BFS를 진행한다. 이때 조건은 크게 4가지로 분류한다. [두 동전의 다음 위치 탐색 없이] (1) 두 동전 모두 벽에 부딪..

문제 링크 : www.acmicpc.net/problem/17836 17836번: 공주님을 구해라! 용사는 마왕이 숨겨놓은 공주님을 구하기 위해 (N, M) 크기의 성 입구 (1,1)으로 들어왔다. 마왕은 용사가 공주를 찾지 못하도록 성의 여러 군데 마법 벽을 세워놓았다. 용사는 현재의 가지고 있는 www.acmicpc.net 문제 풀이는 다음과 같다. (1) 벽을 부수고 방문하는 기록과 벽을 부수지 않고 방문하는 기록을 모두 저장할 수 있도록, 3차원 bool문을 만들어준다. ex : bool ch[101][101][2] -> 여기서 맨 뒤의 2가 벽을 부쉈는지 아닌지를 결정한다. (2) BFS를 진행한다. 이때 목표 지점인 (n,m)에 도달할 경우, 어차피 BFS는 가장 작은 값, 즉, 가장 빨리 목..

링크 : www.acmicpc.net/problem/13460 13460번: 구슬 탈출 2 첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B' www.acmicpc.net 문제의 핵심 포인트는 다음과 같다. 1. 빨간공만 들어간 경우 2. 빨간공과 파란공이 같이 들어간 경우 3. 파랑공만 들어간 경우 이 세가지를 구분하여 코드를 작성해야하는데, 구분에만 집중하다가는 코드가 너무 길어지고 필요없는 변수들이 여러번 생성될 수 있다. 이 문제는 소스를 분석하며 해석하도록 하겠다. #include #include #include..

링크 : programmers.co.kr/learn/courses/30/lessons/43164 코딩테스트 연습 - 여행경로 [[ICN, SFO], [ICN, ATL], [SFO, ATL], [ATL, ICN], [ATL,SFO]] [ICN, ATL, ICN, SFO, ATL, SFO] programmers.co.kr 분류 : 깊이/너비 우선 탐색 (DFS/BFS) 이 문제는 제한사항들 중에서 서로 충돌하는 포인트가 있다. 만일 가능한 경로가 2개 이상일 경우 알파벳 순서가 앞서는 경로를 return합니다. 주어진 항공권은 모두 사용해야 합니다. 이 두 조건을 동시에 고려하지 않고 문제를 풀면 아래와 같은 예시에서 충돌이 발생한다. 입력값 : [["ICN", "AAA"], ["AAA", "CCC"], [..

링크 : www.acmicpc.net/problem/7569 7569번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, www.acmicpc.net 이 문제는 #7576번 토마토의 확장판이다. 풀이 방식은 7576번과 큰 차이가 없다. 다만 입력받는 배열에 Z축이 하나 추가되었을 뿐이다. 문제 풀이는 다음과 같다. 배열을 2개 만든다. 하나는 값을 입력받을 값(arr), 다른 하나는 방문 여부를 파악하고 동시에 토마토가 익을 날짜를 누적할 배열(ch)이다. 배열에 값을 넣는다. 이때 ch(방문여부를 파악하며 동시에 가 토마토..

링크 : programmers.co.kr/learn/courses/30/lessons/43163 코딩테스트 연습 - 단어 변환 두 개의 단어 begin, target과 단어의 집합 words가 있습니다. 아래와 같은 규칙을 이용하여 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾으려고 합니다. 1. 한 번에 한 개의 알파벳만 바꿀 수 programmers.co.kr 분류 : 깊이/너비 우선 탐색 (DFS/BFS) #include #include #include using namespace std; int solution(string begin, string target, vector words) { int answer = 0; queue q; q.push(make_pair(begin,0..

링크 : programmers.co.kr/learn/courses/30/lessons/43162 코딩테스트 연습 - 네트워크 네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어있고, 컴퓨터 B와 컴퓨터 C가 직접적으로 연결되어 있�� programmers.co.kr 분류 : 깊이/너비 우선 탐색 (DFS/BFS) 이 문제는 배열, 혹은 벡터를 넘겨줄때 Call by value가 아닌 Call by reference로 넘겨줘야한다. 깊이 생각하지 않고 코드를 작성하다가 무작정 Call by value로 적어낸 덕에 탈락을 맞이했고, 곰곰이 생각한 후에 Call by value로 벡터를 넘긴 탓에 v[x][x]=0이라는 값..

링크 : www.acmicpc.net/problem/7562 7562번: 나이트의 이동 체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 �� www.acmicpc.net 전형적인 BFS문제. 이 문제에서는 체스말의 위치값의 한 쌍 (x,y) 그리고 누적된 이동값 Num을 같이 저장하기 위해 1개의 요소와 2개의 요소를 pair형태로 Queue에 저장한 점이 인상깊었다 queue q; q.push(make_pair(0,make_pair(y,x))); #include #include #include #include #include using namespace std; ..

링크 : www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로�� www.acmicpc.net 고려해야할 조건은 다음과 같다. (1) 이동하려는 다음 칸이 벽 && 아직 벽을 부순적이 없슴 -> 벽을 부쉈다고 표시해주고 큐에 넣어서 다음 단계 진행 (2) 이동하려는 다음 칸이 벽 && 벽을 부순적이 있슴 -> 진행 불가능. 큐에 넣지 않고 진행 -> 즉, 별도의 if문을 통해 작업이 진행되지 않는다. (3) 이동하려는 다음 칸이 통로 && 아직 벽을 부순적이 없슴 -..