개발하는 고라니

1303번: 전쟁 - 전투 첫째 줄에는 전쟁터의 가로 크기 N, 세로 크기 M(1 ≤ N, M ≤ 100)이 주어진다. 그 다음 두 번째 줄에서 M+1번째 줄에는 각각 (X, Y)에 있는 병사들의 옷색이 띄어쓰기 없이 주어진다. 모든 자리에는 www.acmicpc.net [DFS or BFS] 2차원 배열이 map으로 주어지는 문제에서는 늘 BFS로 풀었어서 이번엔 DFS로 풀어보았다. B와 W로 이루어진 지도를 char로 그대로 저장하지 않고 boolean으로 저장하였다. W 이면 true로, B이면 false로. 물론 char[][]로 저장하여도 상관없다. 이제 2차원 배열 모든 정점을 방문할 차례인데, B로 이루어진 덩어리와 W로 이루어진 덩어리의 개수를 Math.pow해서 반환하도록 했다. DFS..

17090번: 미로 탈출하기 크기가 N×M인 미로가 있고, 미로는 크기가 1×1인 칸으로 나누어져 있다. 미로의 각 칸에는 문자가 하나 적혀있는데, 적혀있는 문자에 따라서 다른 칸으로 이동할 수 있다. 어떤 칸(r, c)에 적힌 문 www.acmicpc.net [DFS + 동적 프로그래밍] 동적 프로그래밍을 사용하지 않고 DFS만 가지고도 충분히 해결할 수 있는 문제이다. 하지만 메모제이션을 사용하지 않으면 N x M의 각 좌표에서 다른 정점을 타고 탈출할 수 있는지 여부를 확인하기 위해 다른 정점에서 방문했었던 정점을 똑같이 방문하고, 방문하고... 이러한 반복적인 방문을 해결하기 위해, 특정 정점에서 탈출할 수 있다면 탈출할 수 있다고 체크를 한다면, 그 정점을 다시 방문했을 때 '아 여기서는 탈출할..

1501번: 영어 읽기 첫째 줄에 사전에 있는 단어들의 개수 N(0 ≤ N ≤ 10,000)이 주어진다. 다음 N개의 줄에는 각 줄에 하나씩, 영어 사전에 있는 단어들이 주어진다. 각 단어의 길이는 100자를 넘지 않는다. 다음 줄에 www.acmicpc.net [문자열 + 해싱] 나는 주어진 단어들을 소인수 분해하듯 알파벳 별로 나누어 배열에 저장하였다. 해싱이라고 하기도 뭐하지만.. 입력으로 주어지는 단어는 알파벳 대소문자로만 이루어져있기 때문에 뜻밖의 변수는 없을 것이다. a의 아스키코드는 97이고, A의 아스키코드는 65이다. 따라서 단어를 받으면 맨 앞, 맨 뒤 글자를 제외한 중간 문자열을 char로 변환해 'a'를 빼주었다. 그러면 0~25가 나올 수도 있고, 음수가 나올 수도 있는데 음수가 ..

1068번: 트리 첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다 www.acmicpc.net [DFS] 문제의 주어진 입력을 토대로 N x N 크기의 단방향 인접 행렬을 만들었다. 그리고 마지막 줄에서 제거할 노드의 번호를 입력 받는데, 이 때 제거할 노드를 방문 했다고 처리한다. 이제 DFS를 수행할 차례인데, 만약 root 노드와 제거할 노드가 동일하다면 DFS를 수행해서는 안된다. 따라서 root노드와 제거할 노드가 다르다면 DFS를 수행한다. 이때 DFS는 다음과 같은 로직을 갖는다. static void DFS(int x){ visit[x..

17071번: 숨바꼭질 5 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 500,000)에 있고, 동생은 점 K(0 ≤ K ≤ 500,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 www.acmicpc.net [BFS] 백준의 숨바꼭질 문제 시리즈 중 거의 마지막 문제. 이전의 문제들과는 더욱 꼬아져있다. 수빈이가 움직이는 것은 동일하지만, 이번엔 동생이 움직인다. 그것도 가속도가 붙어서 움직인다. 일반적인 BFS는 한번 방문한 정점에 대하여 다시는 방문하지 않는다. 예를 들어 수빈이가 15를 2초만에 도착했다고 하자. 동생이 15를 4초만에 도착했다고 했을 때 일반적인 BFS라면 수빈이는 동생을 금방 만날 수 있음에도 불구하고 저..

14496번: 그대, 그머가 되어 첫째 줄에 머호가 바꾸려 하는 문자 a와 b가 주어진다. 둘째 줄에 전체 문자의 수 N과 치환 가능한 문자쌍의 수 M이 주어진다. (1

12904번: A와 B 수빈이는 A와 B로만 이루어진 영어 단어가 존재한다는 사실에 놀랐다. 대표적인 예로 AB (Abdominal의 약자), BAA (양의 울음 소리), AA (용암의 종류), ABBA (스웨덴 팝 그룹)이 있다. 이런 사실에 놀란 수 www.acmicpc.net [문자열 + BFS] 이 문제는 정공법으로 풀면 안된다. s -> t를 가는게 아닌, t -> s를 가는 것을 생각해야 한다. 전자로 풀면 메모리 초과가 날 수 있다. 따라서 t -> s로 가는 방법으로 풀어보자. 1. 문자열의 끝이 'A'이면 맨 끝 문자 삭제 2. 문자열의 끝이 'B'이면 맨 끝 문자 삭제 후 뒤집기 나는 Set을 이용해 방문을 표시했엇으나, 굳이 필요하지 않음을 느꼈다. 따라서 반복문의 종료 조건은 문자열..

4358번: 생태학 프로그램은 여러 줄로 이루어져 있으며, 한 줄에 하나의 나무 종 이름이 주어진다. 어떤 종 이름도 30글자를 넘지 않으며, 입력에는 최대 10,000개의 종이 주어지고 최대 1,000,000그루의 나무가 주어 www.acmicpc.net [문자열 + Map] 우선 문제의 입력은 마지막이 특별한 조건이 없으므로 입력받은 값이 Null 또는 공백일 때 입력을 종료한다. 나는 BufferedReader를 썻지만, Scanner를 사용한다면 hasNextLine()을 사용할 수 있을지도 모르겠다. Map을 이용해서 나무 이름으로 Key를, 그 나무 이름이 나오는 횟수를 Value로 설정하고 값을 계속 업데이트하자. 그러면 해당 나무가 몇 번 이름 불렸는지 알게되는데, 문제에서는 이름 순으로 ..