-
BOJ 9177 단어 섞기알고리즘/백준 2022. 1. 26. 19:29
9177번: 단어 섞기
입력의 첫 번째 줄에는 1부터 1000까지의 양의 정수 하나가 주어지며 데이터 집합의 개수를 뜻한다. 각 데이터집합의 처리과정은 동일하다고 하자. 각 데이터집합에 대해, 세 개의 단어로 이루어
www.acmicpc.net
오래전에 풀지 못했던 문제를 해결하는 과정에서 문자열인데 DFS를 사용한다는 것이 내 입장에서는 특이한 것 같았다.
이 문제를 맨 처음 풀었을 때, 나는 단순히 세 번째 단어의 길이만큼 조사하여 이러한 경우들을 그대로 반영했다.
1. 첫 번째 단어의 현재 위치의 문자와 같을 경우
2. 두 번째 단어의 현재 위치의 문자와 같을 경우
여기서 맨 처음 떠올랐던 건 두 단어 문자가 같을 경우는 어떻게 하지?라는 점이었고, 이를 위해서 나는
1번의 조건에 이와 같은 조건을 추가하여, 만약 같을 경우 두 번째 단어의 문자를 넣어줬다.
일단 맨 처음 이 문제를 버렸던 이유는 런타임 에러였는데, 최근 백준에서는 Exception을 가르쳐줬기 때문에, 이를 알아본 결과 charAt에 대해서 길이가 초과되는 점이 있는 것으로 생각했다.
그래서 이를 고쳐보니 아예 이 생각이 틀렸다는 것을 알 수 있었다.
이건 내가 짜놓은 틀이고, 만약 두 번째 단어가 들어가야 할 것이 아니라 첫 번째 단어의 문자가 들어갔어야 한다면?
그건 다음 문자를 보고 판단해야하는데 그럼 그건 어떻게 해야 할까?
라는 생각이 들었고, 그래서 코드를 갈아엎었다.
그리고 방법을 생각해보니, 이건 아예 모든 경우의 수를 다 들여다보는 것이 맞겠다.라는 생각이 들었다. 그래서 이런 경우의 수를 다 따져볼 방법을 생각해보니, 재귀의 방법이 떠올랐고, 뭔가 칸을 이동하는 것이기 때문에 DFS라는 생각이 들었다. 그래서 DFS를 활용해 문제를 풀어보기로 했다.
그래서 내가 짜 놓은 것은 다음과 같다.
if ( ans_now == ans.length() ) { return true; }
일단 가능하다는 전제는 다 돌아봤을 때 현 지점이 세 번째 단어(ans)의 길이와 같게 되면 이는 가능하다는 것이므로 맞다.
if ( s_now < first.length()) { char s = first.charAt(s_now); if ( s == ans.charAt(ans_now)) { a_check = DFS(s_now+1, e_now, ans_now+1); } else { a_check = false; } }
이는 첫 번째 단어의 현 지점이 세 번째 단어의 지점과 같을 경우이고, 만약 같다면 첫 번째 단어는 다음 지점을 가리키게 하고, 세 번째 단어 또한 다음 지점을 가리킨다.
두 번째 단어 역시 이렇게 코드를 짰고, 그 결과는 시간 초과였다.
솔직히 여기서부터는 방법이 떠오르지 않았다. 사실 예상은 했었는데, 모든 경우의 수를 다 돌아보는 것이기 때문에 아무리 단어들의 최대 길이가 200자라고 하더라도 최대 길이가 400이 되는 세 번째 단어에 도달하기까지 계속 갈래가 2개씩 생기는 것이었기 때문이다.
그러나 이 방법 말고는 생각이 나지 않았고, 이 뒤부터는 도움을 받게 되었다.
1. 만약 첫 번째, 두 번째 단어에 포함되지 않는 문자가 세 번째 단어에 있다면 이는 애초에 완성시킬 수 없는 것이므로 DFS를 사용하지 않는다.
백준 9177. 단어 섞기 :: 돼지개발자 (tistory.com)
백준 9177. 단어 섞기 :: 돼지개발자
출저 : https://www.acmicpc.net/problem/9177 "조금더 빨리 돌아갈 수 있게 최적화를 시키자." 두 개의 문자열을 가지고 다른 문자열을 만들 수 있는지 없는지 확인하는 문제이다. 나는 DFS로 문제를 풀었다
jaejin89.tistory.com
2. 만약 한 번 들렸던 곳이라면 다시 들리지 않게끔 한다. ( visited 배열을 활용. )
boj, 백준) 9177. 단어 섞기 (C / C++) (tistory.com)
boj, 백준) 9177. 단어 섞기 (C / C++)
1. 문제 링크 www.acmicpc.net/problem/9177 9177번: 단어 섞기 세 개의 단어가 주어졌을때, 꿍은 첫 번째 단어와 두 번째 단어를 섞어서 세 번째 단어를 만들 수 있는지 궁금해졌다. 첫 번째와 두 번째 단어
kibbomi.tistory.com
이렇게 해서 문제를 풀었고 정답 처리를 받았다.
'알고리즘 > 백준' 카테고리의 다른 글
BOJ 21921 블로그 (0) 2022.02.11 BOJ 1238 파티 (0) 2022.01.28 BOJ 1613 역사 (0) 2022.01.21 BOJ 11404 플로이드 (0) 2022.01.20 BOJ 11051 이항 계수 2 (0) 2021.12.27