뚝딱뚝딱

https://www.acmicpc.net/problem/7569

토마토 2차원 배열 입력 문제 풀이 참고

2024.01.22 - [CO-TE/백준] - [백준] 7576번 C++ "토마토" 풀이 / BFS, 너비우선탐색

💡 토마토(3차원 배열 입력 ver.)

✅ 문제 풀이

• 이전에 풀었던 토마토 (7576번) 문제와 풀이 방식은 동일한데, 입력으로 주어지는 차원이 3차원으로 늘어나 높이까지 고려해야 한다.
• 따라서 입력을 받는 arr 벡터도 3차원으로 정의해주었고, 좌표를 담는 queue의 자료형도 pair를 한번 더 감싸서 3개의 int 쌍을 갖도록 하였다.
  => pair<pair<int,int>,int>
• 입력으로는 한 판 씩 맨 아래 층 부터 들어오기 때문에 for문의 시작에 for문을 하나 더 추가해서 높이마다 한판 씩 정보를 입력 받도록 하였다.
  = 마지막에 확인할 때도 맨앞에 높이에 대한 for문만 추가해주었다.
•  queue에 push할때도 queue의 자료형에 맞게 두 개의 pair 쌍으로 값을 입력해주었다. 여기서 x 와 y 는 전체 pair에서도 첫번째인 pair 쌍에 해당하기 때문에 front().first.first, front().first.second 로 두번씩 들어가 접근하도록 하였고, z는 전체 pair에서 두번째 값이기 때문에 front().second로 접근하도록 하였다.
• 높이에 대한 조건이 추가되면서, 인접한 범위가 위, 아래 까지 늘어났다. 따라서 총 6번의 탐색을 해야하므로, bfs 함수내에서 사용하는 dx, dy를 수정해주었다. 맨뒤에 높이에 대한 변화가 없도록 {0,0}을 추가해준다. 그리고 높이에 대한 dz를 추가해주고, {0,0,0,0,-1,1} 으로 높이에 대해서만 변화가 있도록 한다.
• bfs 함수 내에서 탐색은 4->6으로 수정해주고, 함수의 인자로는 x,y 뿐만 아니라, z도 받도록 하여, 전체 위치를 표시해준다.
• arr의 인덱스 범위에서도 z는 0이상 h이하에 있도록 검사한다.
• 나머지 로직은 동일하다.

✏ 코드 전문

#include<iostream>
#include<vector>
#include<queue>

using namespace std;

int n, m, h;
vector<vector<vector<int>>> arr;
queue<pair<pair<int, int>,int>> q;
queue<pair<pair<int, int>,int>> temp;

int dx[] = { -1,1,0,0,0,0 };
int dy[] = { 0,0,-1,1,0,0 };
int dz[] = { 0,0,0,0,-1,1 };

int answer = 0;

void bfs(int x, int y, int z) {
	for (int i = 0; i < 6; i++) {
		int nx = x + dx[i];
		int ny = y + dy[i];
		int nz = z + dz[i];

		if (nx >= 0 && nx < n&&ny >= 0 && ny < m&& nz>=0 && nz< h&& arr[nx][ny][nz] == 0) {
			arr[nx][ny][nz] = 1;
			temp.push(pair<pair<int, int>, int> (pair<int, int>(nx, ny),nz));
		}
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> m >> n >> h;

	arr.resize(n, vector<vector<int>>(m, vector<int> (h)));

	for (int k = 0; k < h; k++) {
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				cin >> arr[i][j][k];
				if (arr[i][j][k] == 1) {
					q.push(pair<pair<int, int>, int> (pair<int, int> (i, j), k));
				}
			}
		}
	}

	while (!q.empty()) {
		bfs(q.front().first.first, q.front().first.second, q.front().second);
		q.pop();
		if (q.empty()) {//한번 돌았음을 의미
			answer++;
			while (!temp.empty()) {
				q.push(pair<pair<int, int>, int> (pair<int, int> (temp.front().first.first, temp.front().first.second),temp.front().second));
				temp.pop();
			}
		}
	}

	for (int k = 0; k < h; k++) {
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				if (arr[i][j][k] == 0) {
					cout << -1;
					return 0;
				}
			}
		}
	}

	cout << answer - 1;

	return 0;
}

https://www.acmicpc.net/problem/7576

💡 토마토

✅ 문제 풀이

• BFS를 활용하는 문제이다.
• queue를 사용하여 방문해야 할 곳을 pair<int,int> 형태의 좌표를 저장하도록 하였다.
• 먼저 토마토에 대한 2차원 배열을 순회하면서 값이 1이면 그 위치를 q라는 queue에 pair<int,int> 형태로 넣는다.
• 모두 탐색한 후에는 while문으로 q가 빌때까지 bfs를 수행한다.
• q에서 가장 앞에 있는 front의 first와, second를 bfs의 인자로 넘겨준다.

• BFS함수의 동작
  1. 인자로 받은 위치를 가지고, 동 서 남 북 방향에 있는 값이 배열의 인덱스 범위에 유효하며, 값이 0인지 확인한다.
  2. 위의 조건을 만족한다면 해당 위치의 arr값을 1로 변경해주고, temp라는 이름의 queue에 해당 위치를 pair<int,int> 형태로 넣어준다.

• BFS함수를 돌고 나면 q에서 pop한다.
• 그런다음, 현재 q가 비어있다면, 하루에 익을 수 있는 토마토는 다 익은 것이므로 하루를 카운트 하기 위해 answer를 1 증가시킨다.
• 새로 익어진 토마토에 대한 정보를 가진 temp 있는 위치 정보들을 q에 다 옮겨놓는다.
• 그리고나서 이어지는 다음 while문 동작부터는 다음 날짜에 대한 동작을 진행하는 것이다.
• 그런데, q가 비어지게 되면 temp가 비어있고, 그날이 마지막 날이었더라도 하루가 무조건 더해지게 되기 때문에, 마지막에는 answer에서 1을 뺀 값이 답이된다.
• while문을 모두 수행하고 나면, 갱신된 2차원 배열을 순회하면서, 하나라도 0이 있는 값이 있는지 찾아본다.
• 이는 0이 하나라도 있다면 모든 토마토가 익어질 수 없다는 뜻이므로 -1을 출력하고 프로그램을 종료하기 위함이다.
• 그렇지 않다면 answer-1을 출력하도록 하여, 토마토 판에서 토마토가 다 익는데 걸리는 날을 출력한다.

✏ 코드 전문

#include<iostream>
#include<vector>
#include<queue>

using namespace std;

int n, m;
vector<vector<int>> arr;
queue<pair<int, int>> q;
queue<pair<int, int>> temp;

int dx[] = { -1,1,0,0 };
int dy[] = { 0,0,-1,1 };
int answer = 0;

void bfs(int x, int y) {
	for (int i = 0; i < 4; i++) {
		int nx = x + dx[i];
		int ny = y + dy[i];
		if (nx >= 0 && nx < n&&ny >= 0 && ny < m&&arr[nx][ny] == 0) {
			arr[nx][ny] = 1;
			temp.push(pair<int, int>(nx, ny));
		}
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> m >> n;

	arr.resize(n,vector<int>(m));

	bool end = true;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> arr[i][j];
			if (arr[i][j] == 1) {
				q.push(pair<int,int>(i, j));
			}
		}
	}

	while (!q.empty()) {
		bfs(q.front().first, q.front().second);
		q.pop();
		if (q.empty()) {//한번 돌았음을 의미
			answer++;
			while(!temp.empty()) {
				q.push(pair<int,int>(temp.front().first, temp.front().second));
				temp.pop();
			}
		}
	}

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (arr[i][j] == 0) {
				cout << -1;
				return 0;
			}
		}
	}

	cout << answer-1;

	return 0;
}

https://www.acmicpc.net/problem/2178

💡 미로 탐색

N×M크기의 배열로 표현되는 미로가 있다.

미로에서 1은 이동할 수 있는 칸을 나타내고, 0은 이동할 수 없는 칸을 나타낸다. 이러한 미로가 주어졌을 때, (1, 1)에서 출발하여 (N, M)의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구하는 프로그램을 작성하시오. 한 칸에서 다른 칸으로 이동할 때, 서로 인접한 칸으로만 이동할 수 있다.위의 예에서는 15칸을 지나야 (N, M)의 위치로 이동할 수 있다. 칸을 셀 때에는 시작 위치와 도착 위치도 포함한다.

[입력]
첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다.

[출력]
첫째 줄에 지나야 하는 최소의 칸 수를 출력한다. 항상 도착위치로 이동할 수 있는 경우만 입력으로 주어진다.

✅ 문제 풀이

• 처음에 시간초과가 발생했던 접근법

1. miro라는 함수를 호출하여 (0,0)부터 출발하고, 동,서,남,북에 있는 값이 1이면 각각의 위치에서 miro함수를 재귀호출하는 방식을 통해 count해 나간다.
2. 만약 miro함수에서 현재 위치가 (n-1,m-1)이면 현재까지의 count값과 answer값을 비교해서 작은 것을 answer로 갱신한다.

-> 이렇게 되면 n이 커질수록, 재귀호출 양이 많아져 시간 초과가 발생한다.

• queue를 이용해 재귀호출을 하지않고 count하는 방식으로 문제를 해결!

1. miro함수에 queue를 하나 생성한다. 
   이 queue는 pair로 <<행,렬>, count>로 데이터를 갖고 있다.
2. queue에 {{0,0},1}을 추가해서 (0,0)위치에서 1카운트 된 것을 queue에 집어넣는다.
3. 다음의 과정은 queue가 빌때까지 실행한다.
4. queue의 front에서 행의 값을 r에, 열의 값을 c에, count를 count에 넣는다.
5. 이제 여기는 방문한 것이므로 arr값을 0으로 바꾸어준다.
6. 현재 위치가 (n-1,m-1)인지 확인해서 맞다면, 현재의 count값과 기존의 최소 count가 저장된 answer를 비교해서 더 작은 값으로 갱신해준다.
7. 그리고 for문을 통해 현재 위치에서 상,하,좌,우에 있는 값이 1이면 queue에 해당 좌표와 현재의 count에서 +1한 값을 카운트로 넣어주고, 방문했음을 표시하기 위해 해당 위치의 arr값도 0으로 갱신해준다.
8. miro함수가 끝나고 나면 answer에는 최소 이동 값만이 저장된다.

✏ 코드 전문

#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<queue>

using namespace std;

int n, m;

int answer = 10000;

int dx[] = { -1,1,0,0 };
int dy[] = { 0,0,-1,1 };

void miro(vector<vector<int>> &arr) {
	queue<pair<pair<int, int>, int>> q;
	q.push({ { 0, 0 }, 1 });
	arr[0][0] = 0;

	while (!q.empty()) {
		int r = q.front().first.first;
		int c = q.front().first.second;
		int count = q.front().second;

		q.pop();

		if (r == n - 1 && c == m - 1) {
			answer = min(answer, count);
			return;
		}

		for (int i = 0; i < 4; i++) {
			int x = r + dx[i];
			int y = c + dy[i];
			if (x >= 0 && x < n&&y >= 0 && y < m&&arr[x][y] == 1) {
				q.push({ {x,y}, count + 1 });
				arr[x][y] = 0;
			}
		}

	}

}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> n >> m;

	vector<vector<int>> arr(n);

	for (int i = 0; i < n; i++) {
		string str;
		cin >> str;
		for (int j = 0; j < str.length(); j++) {
			arr[i].push_back(str[j] - '0');
		}
	}

	miro(arr);

	cout << answer;
}

https://www.acmicpc.net/problem/1260

💡 DFS와 BFS

그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다.

[입력]
첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다.

[출력]
첫째 줄에 DFS를 수행한 결과를, 그 다음 줄에는 BFS를 수행한 결과를 출력한다. V부터 방문된 점을 순서대로 출력하면 된다.

✅ 문제 풀이

• DFS와 BFS의 로직을 나누어서 두번의 결과를 따로 구하고 출력하도록 하였다.
• 일단 입력으로 받은 간선의 정보를 2차원 벡터에 저장하였다.
  이때 양방향 간선이라는 점을 고려하여, A->B로 B->A로의 간선 정보를 저장해준다.
• S노드에서 시작하므로, S번의 visited를 true로 설정하고 시작한다.
• 간선 정보를 담은 arr배열을, 각 노드에 대해서 오름차순 정렬해준다. 노드 번호가 낮은 것부터 방문해야 하기 때문이다.
• dfs함수는, arr배열의 s번 vector를 탐색하는데, 먼저 방문하는 노드를 시작으로 또 dfs를 재귀호출하며 방문하도록 한다. 
• bfs함수는, arr배열의 s번 vector를 탐색하는데, 각 노드를 탐색할 때마다 queue에 담아주고, 해당 벡터를 다 탐색하고 나서는 queue의 front부터 탐색하며 bfs를 재귀호출하도록 한다.
• 각각의 결과는 dfs_result, bfs_result에 담은 후 출력한다.

✏ 코드 전문

#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>

using namespace std;

void dfs(int s, vector<vector<int>> arr, vector<bool> &visited, vector<int> &dfs_result) {
	for (int i = 0; i < arr[s].size(); i++) {
		if (!visited[arr[s][i]]) {
			visited[arr[s][i]] = true;//방문
			dfs_result.push_back(arr[s][i]);
			dfs(arr[s][i], arr, visited, dfs_result);
		}
	}
}
void bfs(int S, vector<vector<int>> arr, vector<bool> &visited, vector<int> &bfs_result, queue<int> &q) {
	for (int i = 0; i < arr[S].size(); i++) {
		if (!visited[arr[S][i]]) {
			visited[arr[S][i]] = true;//방문
			q.push(arr[S][i]);
			bfs_result.push_back(arr[S][i]);
		}
	}
	while (!q.empty()) {
		int next = q.front();
		q.pop();
		bfs(next, arr, visited, bfs_result, q);
	}
}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int N, M, S;
	cin >> N >> M >> S;

	vector<vector<int>> arr(N+1);
	vector<bool> visited1(N + 1, false);//dfs에서사용
	vector<bool> visited2(N + 1, false);//bfs에서사용
	queue<int> q;//bfs에서 사용
	vector<int> dfs_result;
	vector<int> bfs_result;
	for (int i = 0; i < M; i++) {//간선 정보 입력받기
		int n1, n2;
		cin >> n1 >> n2;

		arr[n1].push_back(n2);
		arr[n2].push_back(n1);
	}

	for (int i = 1; i < N + 1; i++) {//노드별로 간선 정보를 오름차순 정렬
		sort(arr[i].begin(), arr[i].end());
	}


	visited1[S] = true;
	visited2[S] = true;
	dfs_result.push_back(S);
	bfs_result.push_back(S);

	dfs(S, arr, visited1, dfs_result);
	bfs(S, arr, visited2, bfs_result, q);

	for (int i = 0; i < dfs_result.size(); i++) {
		cout << dfs_result[i]<<" ";
	}
	cout << "\n";
	for (int i = 0; i < bfs_result.size(); i++) {
		cout << bfs_result[i] << " ";
	}
	
	return 0;
}

여행 경로

💡문제

주어진 항공권을 모두 이용하여 여행경로를 짜려고 합니다. 항상 "ICN" 공항에서 출발합니다. 항공권 정보가 담긴 2차원 배열 tickets가 매개변수로 주어질 때, 방문하는 공항 경로를 배열에 담아 return 하도록 solution 함수를 작성해주세요.


주어진 항공권은 모두 사용해야 합니다.
만일 가능한 경로가 2개 이상일 경우 알파벳 순서가 앞서는 경로를 return 합니다.
모든 도시를 방문할 수 없는 경우는 주어지지 않습니다.

딱 보자마자 모든 경로를 탐색해야 하기 때문에, dfs를 사용해야 한다는 점은 알아야 한다.

그런데, 문제를 보면, 여러개의 경로가 나올 시 사전 순으로 앞서는 경로를 return해야 한다.

여러개의 경로를 구해두고 그 중에서 알파벳 순으로 먼저인 경로가 앞으로 오도록 정렬한 후 맨 앞에 있는 것을 선택해야한다.

따라서 이 문제는 BFS도 적용해야 한다.(위에서 말한 바와 같이 정렬만 하면 되긴 한다)

다음과 같은 단계로 진행할 수 있다.

1. 여러가지 경로 자체를 리스트 형태로 여러개 저장할 수 있는 이중 리스트를 생성하자.

static List<List<String>> answerList;

솔루션 함수 밖에서 생성해주었다.

2. 방문 여부를 위한 boolean타입 배열을 선언하자.

static boolean[] visited;

이 역시 솔루션 함수 밖에서 생성해주었다.

3. 이제 이중리스트에 ArrayList로 동적 할당해주고, 방문 배열 역시 tickets배열 크기만큼 동적 할당하자.

answerList = new ArrayList<>();
visited = new boolean[tickets.length];

솔루션 함수 내로 들어왔다.

4. 이제 tickets 배열을 순회하면서 출발지가 "ICN"인지 확인하자.

for (int i = 0; i < tickets.length; i++) {
            if (tickets[i][0].equals("ICN")) {

5. 조건에 만족한다면, 경로를 저장하기 위한 list를 생성하고 동적할당한다. 그리고 출발지인 "ICN"을 담는다.

현재 노드를 방문한 것이므로 visited[i]를 true로 하고, 리스트에는 해당 노드의 도착지를 저장한다.

List<String> list = new ArrayList<>();
list.add("ICN");
visited[i] = true;
list.add(tickets[i][1]);

6. 도착지인 tickets[i][1]이 다시 출발지가 되어 다음 노드를 방문해야 한다. 따라서 아직 방문하지 않은 노드들 중 출발지가 tickets[i][1]인 노드를 찾아 위의 과정을 반복하자. 이를 dfs함수에 구현하자.

public void dfs(String[][] tickets, int begin, List<String> list) {
        if (list.size() == tickets.length + 1) {
            answerList.add(new ArrayList<>(list));
            return;
        }
        
        for (int i = 0; i < tickets.length; i++) {
            if (!visited[i] && tickets[i][0].equals(tickets[begin][1])) {
                visited[i] = true;
                list.add(tickets[i][1]);
                dfs(tickets, i, list);
                visited[i] = false;
                list.remove(list.size() - 1); // 백트래킹
            }
        }
    }

   - dfs함수는 tickets와 출발지 인덱스, 진행중이던 경로 list에 대한 정보를 받는다.

   - 만약 현재 list의 크기가 tickets의 길이보다 1 큰 것과 같다면, 모든 tickets를 고려한 것이기 때문에, 이중 리스트인 answerList에 list를 넣는다. = 경로 모음집에 경로를 하나 추가한 것이다.

   - 아직 tickets를 다 방문하지 않았다면, 모든 노드에 대해서, 아직 방문하지 않았고, 인자로 받은 출발지를 갖는 노드를 방문한다.

   - 역시 list에 방문한 노드의 도착지를 넣어준다 (출발지는 이전 단계에서의 도착지로, 이미 넣어졌기 때문이다)

   - 그리고 그 도착지를 기점으로 다시 dfs를 호출해서 반복되도록 해준다.

   - 다 돌고 나서 다시 다른 경로를 순회하기 위해 다시 visited[i]를 false로 바꾸어주는 단계를 잊어선 안된다.

   - 동일한 원리로 list에서도 제거해준다.

7. 다시 solution함수로 돌아오자. 방금 전까지 dfs가 어떻게 돌아가는지를 확인하였다. 이 dfs를 최초로 불러주자.

dfs(tickets, i, list);
visited[i] = false;

   - 여기에서도 dfs를 돌고난 후 혹시 다른 경로를 먼저 방문했을 시를 고려해서 visited[i]를 false로 바꿔주는 것을 잊지 말자.

8. 이렇게 가능한 경로를 다 구했으면, List에 들어있는 경로들을 알파벳 순으로 정렬해주자.

Collections.sort(answerList, (a, b) -> {
            for (int i = 0; i < a.size(); i++) {
                int compare = a.get(i).compareTo(b.get(i));
                if (compare != 0) {
                    return compare;
                }
            }
            return 0;
});

   - Collections의 sort함수를 사용할건데, 람다식을 이용해서 모든 경로에 대해 각각의 첫번째부터 끝번째 노드까지 알파벳 순을 비교해서 빠른것이 앞으로 오도록 설계한다.

9. 이제 answerList의 맨 첫번째 경로가 asnwer가 될 것이다. 이 경로 하나를 가져오기 위해 answer를 list로 선언하고 answerList의 0번째 리스트를 가져와 할당한다. 그리고 list의 toArray함수를 통해 answer를 배열 형태로 반환하도록 한다.

List<String> answer = answerList.get(0);

return answer.toArray(new String[answer.size()]);

이렇게 해서 모든 경로를 탐색하고, 정렬을 통해 알파벳 순으로 가장 빠른 경로를 찾아낼 수 있었다.

전체 코드는 아래와 같다.

import java.util.*;

class Solution {
    static List<List<String>> answerList;
    static boolean[] visited;
    
    public String[] solution(String[][] tickets) {
        answerList = new ArrayList<>();
        visited = new boolean[tickets.length];
        
        for (int i = 0; i < tickets.length; i++) {
            if (tickets[i][0].equals("ICN")) {
                List<String> list = new ArrayList<>();
                list.add("ICN");
                visited[i] = true;
                list.add(tickets[i][1]);
                dfs(tickets, i, list);
                visited[i] = false;
            }
        }
        
        // 결과로 반환할 경로 선택 (알파벳 순서가 앞서는 경로)
        Collections.sort(answerList, (a, b) -> {
            for (int i = 0; i < a.size(); i++) {
                int compare = a.get(i).compareTo(b.get(i));
                if (compare != 0) {
                    return compare;
                }
            }
            return 0;
        });

        List<String> answer = answerList.get(0);

        return answer.toArray(new String[answer.size()]);
    }
    
    public void dfs(String[][] tickets, int begin, List<String> list) {
        if (list.size() == tickets.length + 1) {
            answerList.add(new ArrayList<>(list));
            return;
        }
        
        for (int i = 0; i < tickets.length; i++) {
            if (!visited[i] && tickets[i][0].equals(tickets[begin][1])) {
                visited[i] = true;
                list.add(tickets[i][1]);
                dfs(tickets, i, list);
                visited[i] = false;
                list.remove(list.size() - 1); // 백트래킹
            }
        }
    }
}

이제 DFS문제를 3-4번 풀어보니, 어느정도 감이오고, 문제를 읽어보면 DFS로 풀어야하는지 알 수 있게 되었다.

확실히 BFS보다 DFS의 비중이 더 많은 것 같기도 하다.

그리고 자바 문법은 더 꼼꼼히 살펴보아야겠다!!

코테를 보고나서 DFS의 중요성을 뼈저리게 느끼고, 한 번 더 개념을 잡고, 흐름을 잡고자 풀어본 문제이다.

✅ 코테에서 머뭇거렸던 부분

• DFS함수를 어느 시점에서 불러야 할지
• DFS함수를 어떻게 구성해야 할지
  (함수 내에서 재귀적으로 호출하는 부분은 어떻게?)
  (해당 노드를 방문할지 말지를 어떻게?)
• 방문하고 나서 다시 이전 단계로 돌아와 다른 경로를 찾게 하려면 코드를 어떻게?⭐⭐⭐(이게 관건임)

위와 같은 이유들은 내가 dfs를 스택으로 해결한 문제만 풀어봤기 때문이고, dfs함수를 써서 재귀적으로 함수를 호출하며 방문 여부를 체크하는 배열을 사용한 문제를 접해보지 못했기 때문에, 그 로직을 정확히 이해하지 못한 것 같다.

이 문제를 계기로 dfs의 전체적인 흐름을 바로잡고자 한다.

💡 문제

두 개의 단어 begin, target과 단어의 집합 words가 있습니다. 아래와 같은 규칙을 이용하여 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾으려고 합니다.

1. 한 번에 한 개의 알파벳만 바꿀 수 있습니다.
2. words에 있는 단어로만 변환할 수 있습니다.

예를 들어 begin이 "hit", target가 "cog", words가 ["hot","dot","dog","lot","log","cog"]라면 "hit" -> "hot" -> "dot" -> "dog" -> "cog"와 같이 4단계를 거쳐 변환할 수 있습니다.
두 개의 단어 begin, target과 단어의 집합 words가 매개변수로 주어질 때, 최소 몇 단계의 과정을 거쳐 begin을 target으로 변환할 수 있는지 return 하도록 solution 함수를 작성해주세요.


변환할 수 없는 경우에는 0를 return 합니다.

다음과 같은 것을 고려해 볼 수 있다.

1. 현재 begin과 비교했을 때 words 중에 딱 한 문자만 다른 단어가 있는지?
   => 이를 위한 함수가 필요하다.
2. 만약 한문자만 다른 단어가 있으면 그 단어에서 다음 변경될 단어를 찾을 때 역시 한 문자만 다른지를 확인해야하고, 그 문자를 방문한 이력이 있는지를 확인해야한다.
   =>해당 단어를 방문한 이력이 있는지를 기록하는 boolean타입의 배열이 필요하다.
3. 조건에 맞는 단어를 방문하고 나서 다음 방문 여부를 확인하고 이어서 또 방문하기 위해선 dfs함수안에 dfs함수를 재귀적으로 호출하여 해당 루트에 대해 끝까지 방문하도록 해야한다.
4. 재귀함수이더라도 끝은 있어야 한다. dfs함수 내에 if문으로, 현재 방문한 단어가 target과 같을 시에는 answer를 갱신하고 dfs를 빠져나오도록 한다.
5. 항상 dfs를 재귀로 호출한 다음에는, 이전 단계로 돌아왔을 때 다른 루트를 고려하기 위해서 해당 노드의 방문여부를 다시 false로 바꾸어주는 단계가 필요하다.(=이것은 즉, 이 노드를 방문하지 않았다면?과 같은 의미이다=>이어지는 다음 루프에서는 해당 노드를 방문하지 않은채로 고려할 수 있기 때문이다⭐⭐⭐)

✏ [5에 대한 부가 설명]

1,2,3 노드가 있다고 하자.
현재 1번 노드를 방문한 상태이고, 앞으로 방문기록이 없는 2와 3에 대해 방문을 할것이다.
for문을 통해 번호순으로 방문할 것이기 때문에, 2를 먼저 방문한다.
2를 방문했으므로 visited배열에 2를 방문했다는 표시(true)를 한다.
그리고 다시 2를 시작으로 남은 노드를 순차적으로 방문한다. 
현재 예시에서는 방문기록이 없는것 중 남은게 3뿐이므로 3을 방문한다.
더이상 방문할 곳이 없기 때문에 다시 이전 단계로 돌아가 본다.
2를 다시 방문하지 않은 상태로 둔다.
하지만 이전 for루프에서는 순차적으로 2를 방문한 것이었고, 이번 for루프에서는 3을 방문할 차례이다.
따라서 3을 방문하고, visited배열에 3을 방문했다는 표시를 한다.
그리고 다시 3을 시작으로 남은 노드를 순차적으로 방문한다.
현재 방문기록이 없는게 2뿐이므로 2를 방문한다.

이렇게 되면 1->2->3으로 한번 방문했고, 1->3->2로도 한번 방문했다.
이런식으로 첫 시작이 잡히면 그 뒤로 방문처리, 재귀적으로 호출, 다시 미방문처리, 다음루프 로 이어지면서 모든 경로를 탐색해 볼 수 있게 되는 것이다.

위와 같은 사항들을 고려하면서 코드를 작성하면 다음과 같은 단계로 작성할 수 있다.

✅ 코드 작성 단계

1. 간단한 예외 처리해주기.
   - 문제에서 주어진 예시를 보면 words배열에 target이 없는 경우 변환될 수 없는 것이기 때문에, 0을 answer로 리턴하도록 되어 있다.

   - 배열에 해당 요소가 있는지를 비교하면되는데, 이는 ArrayList의 contains() 메서드를 활용하면 매우 쉽다.

list = new ArrayList<>(Arrays.asList(words));//리스트에 Arrays.asList메서드를 통해
//words배열을 리스트로 변경하고 있다
        
if(!list.contains(target)) return 0;//만약 list에서 target이 없으면 0을 리턴

   -list의 경우 List<String> list 로 static 전역으로 선언하여 사용하였다.

2. solution함수 내에서 첫 시작 방문을 for문으로 돌기

   - 어떤 노드가 시작이 될지 모르기 때문에, 시작을 정해주기 위한 모든 경우의 수를 고려해야한다.

   - 따라서 for문을 words의 크기만큼 돌면서 현재 단어가 begin과 한글자만 차이나는지 확인해야 한다.

   - 위를 확인하기 위한 boolean타입의 함수를 생성해주어야 한다.

for(int i=0; i<words.length; i++){//모든 워드에 대해 시작을 탐색
//???

2-1. canChange함수 정의하기

   - 현재 begin 단어가 words의 해당 단어와 한글자만 차이나면 true를, 아니면 false를 반환하도록 하는 함수이다.

   - boolean을 반환한다.

   - for문을 돌면서 begin과 target의 한글자 한글자가 같은지 비교하고, 다르면 count한다.

   - count가 1이면 true를 아니면 false를 반환한다.

public boolean canChange(String target, String begin){//begin과 target을 인자로 받는다
        int count=0;//count는 0으로 초기화한다
        for(int i=0; i<begin.length(); i++){//begin글자수만큼 비교
            if(begin.charAt(i)!=target.charAt(i)) count++;//다르면 카운트
        }
        
        return count==1;//카운트가 1이면 한글자만 차이나는 것이므로 후보가 된다
    }

2-2. 한글자만 차이나는 모든 단어에 대해 해당 단어를 시작으로 하는 루트를 모두 탐색하기

   - 이제 2에서 설명한 for문에서 words 중에 현재 단어가 canChange를 만족하면, visited[] 배열을 새로 할당한다.

   - 해당 단어의 인덱스를 통해 visited에 방문했음을 표시한다.

   - DFS함수를 호출해서 현재 단어를 시작으로 아직 방문하지 않은 나머지 단어에 대해 위 과정을 거치도록 한다.

   - DFS함수를 구현해야 한다.

for(int i=0; i<words.length; i++){
            if(canChange(words[i], begin)){
                visited = new boolean[words.length];
                visited[i]=true;
                dfs(????);
            }
}

3. DFS함수 구현하기

   - dfs함수에서는 사실상 solution함수에 있는 것을 반복하는 것이라고 보면 되는데, 재귀적으로 호출할 것이기 때문에, 마지막에는 멈출 수 있는 조건이 항상 있어야 한다.

   - dfs함수에 현재 루트에서 몇번 노드를 탐색했는지(=answer와 직결됨), 현재 방문한 단어는 무엇인지, 최종 찾고자 하는 (=도달하고자 하는)단어는 무엇인지에 대해 인자로써 알려주어야 한다.

   - 따라서 몇번 노드를 탐색했는지는 int타입의 index, 현재 방문한 단어는 String의 begin, 찾고자 하는 단어는 String의 target이다. 

   - dfs에서는 일단 현재 방문한 노드 begin이 target과 동일한지 비교하고, 동일하면 answer를 갱신한다.

   - 이때 answer는 몇번 노드를 탐색했는지를 나타내는 index와 현재 answer중에 더 작은 것으로 선택하여 갱신하도록 한다. 그리고 return을 하여 dfs가 끝나도록 한다

   - 만약 같지 않다면, for문을 통해 다음 방문할 노드를 찾기 위해 words를 또한번 탐색하는데, visited와 canChange를 통해, 방문한 기록이 없고, 한글자 차이인 경우에는 그 단어를 방문한 상태로 바꿔준다.

   - 그리고 dfs를 호출해서 현재 막 방문한 상태로 바꿔준 단어를 기점으로 위 단계를 반복하도록 한다.

   - 만약 다 돌아서 이전 단계로 돌아왔을 때에는 다시 방문하지 않은 상태로 바꾸어주고, 다음 루프에서 다른 단어를 먼저 방문하더라도 이 노드가 방문될 수 있도록 (즉 여러 루트를 고려하도록 하기 위해, 위에 5번 설명 참고)한다.

   - 위 단계가 매우 중요하다. 이것이 없으면 다시 돌아가서 다른 루트를 찾는 과정을 거칠 수가 없기 때문이다.

public void dfs(int index, String[] words, String begin, String target){
        if(begin.equals(target)){
            answer=Math.min(index, answer);
            return;//이에 해당하면 아래를 실행하지 않기 위해
        }
        
        for(int i=0; i<words.length; i++){
            if(!visited[i]&&canChange(words[i],begin)){
                visited[i]=true;
                dfs(index+1, words, words[i], target);//재귀호출하여 현재 루트를 이어가도록한다
                visited[i]=false;//다른 루트를 탐색하도록 하기 위함이다.매우 중요!!!
            }
        }
    }

4. DFS함수 호출하고, 최종 answer 리턴하기.

   - 앞에서 정의한 dfs에 따라서 인자를 다음과 같이 설정해준다.

   - 첫 방문 노드의 경우 한번 방문했으므로 index는 1이된다. 그리고 방문했을 경우 begin은 words[i]가 되는 것이고, target은 최종 target이다.

for(int i=0; i<words.length; i++){
            if(canChange(words[i], begin)){
                visited = new boolean[words.length];
                visited[i]=true;
                dfs(1,words,words[i],target);
            }
        }
        
        return answer;

   - 이렇게 다 하고 나면 answer에는 최종 답이 들어간다.

5. 세부사항

   - min 연산을 위해 answer는 integer의 max_value로 초기화 하였다.

   - answer, visited배열, list는 static 전역으로 선언하였다.

   - answer는 그래서 모든 연산에서 실시간으로 제일 작은 값을 얻도록 하였다.

최종코드이다.

import java.util.List;
import java.util.ArrayList;
import java.util.Arrays;

class Solution {
    static List<String> list;
    static int answer;
    static boolean[] visited;
    
    public int solution(String begin, String target, String[] words) {
        answer = Integer.MAX_VALUE;
        list = new ArrayList<>(Arrays.asList(words));
        
        if(!list.contains(target)) return 0;
        
        for(int i=0; i<words.length; i++){
            if(canChange(words[i], begin)){
                visited = new boolean[words.length];
                visited[i]=true;
                dfs(1,words,words[i],target);
            }
        }
        
        return answer;
    }
    public void dfs(int index, String[] words, String begin, String target){
        if(begin.equals(target)){
            answer=Math.min(index, answer);
            return;
        }
        
        for(int i=0; i<words.length; i++){
            if(!visited[i]&&canChange(words[i],begin)){
                visited[i]=true;
                dfs(index+1, words, words[i], target);
                visited[i]=false;
            }
        }
    }
    
    public boolean canChange(String target, String begin){
        int count=0;
        for(int i=0; i<begin.length(); i++){
            if(begin.charAt(i)!=target.charAt(i)) count++;
        }
        
        return count==1;
    }
}