https://www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net 문제조건 (1,1) 에서 (n,m)까지 최단경로 벽을 하나까지 부술수있다. 조건 2 때문에 일반적인 bfs로 풀수가 없다. 벽은 부숴도 되고, 안부숴도되고 그렇다면 어떻게 하지,,? 생각을 해보면 bfs자체가 수행될때마다 최단거리를 의미하고, 그에따라 queue에 넣을 조건만 추가해주면 된다. 벽은 하나까지 부술수있으므로, 배열을 3차원배열로 만들어주고, queue에도 (..

https://www.acmicpc.net/problem/12919 12919번: A와 B 2 수빈이는 A와 B로만 이루어진 영어 단어 존재한다는 사실에 놀랐다. 대표적인 예로 AB (Abdominal의 약자), BAA (양의 울음 소리), AA (용암의 종류), ABBA (스웨덴 팝 그룹)이 있다. 이런 사실에 놀란 수빈 www.acmicpc.net 문제조건 A,B로만 이루어진 두 문자열 S, T 가 주어지고, S를 T로 바꾼다. 문자열뒤에 A를 추가한다. 문자열의 뒤에 B를 추가하고 문자열을 뒤집는다. S를 T로 바꿀수 있으면 1 출력, 아니면 0 출력 S에서 두가지 행동만 할 수 있는데 행동들이 전부 문자 길이를 늘리는 것이므로 S, T가 똑같은 길이가 되었을때, 같은 문자열이 아니라면 0을 출력하..

https://www.acmicpc.net/problem/13549 13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 www.acmicpc.net 문제조건 수빈이와 동생이 있다. 걷는다 : X+1 or X-1 (1초) 순간이동 : 2 * X (0초) ☞ 시간 안걸림 수빈이가 동생을 찾는 가장 빠른시간? 문제를 보고 수빈이와 동생이 아닌, 출발지와 목적지로 생각을 바꿔봤다. 그러면 문제가 평소에 익숙하게 보던 최단거리 찾기가 된다. 그러나, 일반적인 최단거리 찾기와 다른 점은 순간이동을 할때는 시간이 안걸..

https://www.acmicpc.net/problem/1157 1157번: 단어 공부 알파벳 대소문자로 된 단어가 주어지면, 이 단어에서 가장 많이 사용된 알파벳이 무엇인지 알아내는 프로그램을 작성하시오. 단, 대문자와 소문자를 구분하지 않는다. www.acmicpc.net 가장 많이 쓴 영어 단어를 대문자로 출력하라. 사실 그냥 문자를 숫자로 취급한 아스키코드로 쉽게 풀어줄 수도 있지만, 저번에 map으로 이런 비슷한 문제를 풀어 봤던것 같아서 map을 써서 풀어 볼 것이다. key-value로 char-int로 두면 각 문자가 등장한 횟수를 쉽게 알 수 있다. #include #include using namespace std; string s; map m; //가장 많이 사용된 알파벳 2개이상일..