붙어서 입력과 BFS

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

BFS 를 통해 최단 거리를 구하는 문제로
정말 단순히 BFS 만 구하고 visited 를 통해 최단 거리를 출력하면 된다.

이때 문제에서 각각의 수들이 붙어서 입력으로 주어진다고 되어있다.

4 6
101111
101010
101011
111011

이런 식으로 수들이 붙어서 입력으로 들어온다는 뜻인데 이는 2가지 방법으로 처리할 수 있다.

• 몇 개를 받는지 아는 경우

int arr[7];

for(int i = 0; i < 7; i++)
	scanf("%1d", &arr[i]);

다음과 같이 몇개를 입력으로 받는지 아는 경우에는 %d 로 들어갈 정수의 개수를 정할 수 있다.

• 몇 개를 받는지 모르는 경우

string str;
cin >> str;

int arr[100];

for(int i = 0; i < str.length(); i++)
	arr[i] = str[i] - '0';

입력을 몇 개를 받는지 모르는 경우 문자열을 통해 하나씩 처리해서 배열에 저장할 수도 있다.

또한 BFS 구현에서 주의할 점은

    while (q.size())
    {
        tie(y, x) = q.front();
        q.pop();
        for (int i = 0; i < 4; i++)
        {
            int ny = y + dy[i];
            int nx = x + dx[i];

            if (ny >= N || ny < 0 || nx >= M || nx < 0 || arr[ny][nx] == 0)
                continue;

            // if (visited[ny][nx] == 1) 은 안됨
            if (visited[ny][nx] > 0)
                continue;
                
            visited[ny][nx] = visited[y][x] + 1;
            q.push({ny, nx});
        }
    }

DFS 나 그래프 구현에서 가중치나 최단 거리를 구하지 않는 경우
visited 를 단순히 1로 만들어 방문 검사를 == 1 로 할 수 있는데

BFS 의 경우 탐색을 진행할수록 visited 의 값이 1에서 증가하므로 위의 조건에는 걸리지 않게 된다.

(당연한거지만 저 부분이 잘못됐다는 것을 알아차리는 데 생각보다 오래걸렸다..)