[백준] 1261번 - 알고스팟 (C++)

• 문제 링크

포스팅 목적

0-1 너비 우선 탐색 알고리즘으로 풀 수 있는 문제다.
풀면서 두 가지 이슈로 삽질했던 경험을 정리해 두려 한다.

---

첫 번째 이슈 : row, column 의미 해석

2차원 배열 또는 행렬을 다룰 때, map[row][col]과 같이 첫 번째 인덱스가 행, 두 번째 인덱스가 열을 가리킨다.

BFS를 활용한 미로찾기 등에서 자주 등장하는 패턴인데, 상하좌우를 이동하기 위해서 아래와 같이 dx, dy배열을 사용한다.

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

문제는 x, y가 좌표평면 상에서 가로, 세로에 해당하는데, 행렬에서는 첫 번째 인덱스인 row가 세로에 해당한다는 것이다. map[y][x]보다는 map[x][y]가 자연스럽기 때문에 많이 헷갈렸다. 심지어는 행렬임에도 map[x][y]성분을 (x, y)로 표현하기도 한다.

근데 헷갈려도 크게 상관 없다는 것이 결론이다. 위의 두 배열은 아래와 같이 사용되는데

int nextRow = row + dx[i]; 
int nextCol = col + dy[i];

해석하기에 따라 상하좌우의 순서만 달라질 뿐이다.
x,y를

• 좌표평면의 가로 세로로 해석하면 위 코드는 하우상좌.
• 행과 열로 해석하면 좌하우상 순이다.

위 코드는 x, y의 자연스러운 순서를 위해서 행과 열로 해석한 것이라 볼 수 있다.
결과는 같더라도 분명히 다른 코드이다. 코드가 어떻게 동작하는지 명확히 알아야 한다.

나처럼 헷갈려 한 사람이 꽤 있는듯하다. 혼동을 야기할 수 있는 이런 것들을 좀 통일해주면 어떻겠냐는 질문에 대한 답을 아래 링크에서 해결할 수 있다.

• 참고 링크

변수나 문자에 의미를 부여하는 것은 사람이다. 스스로 기준을 정해서 혼란스럽지 않으면 어떤 문자를 쓰든지 상관없다. 하지만 부여한 의미를 혼자서만 알면 좋은 코드가 아니기 때문에, 가독성을 위해서 관습을 따르는 것이 좋다. 개발할 때 변수명 정하는게 가장 힘들다는 것이 괜히 나오는 말이 아니다.

---

두 번째 이슈 : 연속된 숫자 입력

'입력따위' 에 관해서 고민하는 단계는 뛰어 넘었다고 자만하던 나를... 일깨워 준 좋은 문제다.
이 문제의 입력이 어떻게 들어오는지부터 보면, 아주 불친절하게도 숫자를 한 줄(행)씩 붙여서 넣어준다. 숫자 하나하나를 내가 떼어내서 2차원 배열에 넣어줘야 한다.

case 1     case 2

011        0001
111        1000
110

되게 쉬운 문제인데, 내가 하고싶었던 것은 C언어의 scanf가 아니라 C++의 cin으로 해결하는 것이었다. C의 입출력이나 구조체를 사용하면 편리하지만, C++이라면 가급적 C++ 문법만 사용하고 싶은 마음이 있다. cin으로 해결하고자 하면서 드러난 부족한 지식을 정리해보자.

char map[101][101];

for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= m; ++j) {
        cin >> map[i][j];
    }
}

연속된 문자열 입력을 받을 때, 문자 하나씩 뜯어내기 위해서 char형 배열을 선언하고 입력받는 방식을 많이 사용했었다. 같은 방식으로 입력을 받은 것인데, 제대로 동작하지 않았다.
그런데 출력해보니 제대로 0과 1이 잘 들어가 있지 않은가? 대체 왜 안 되는거지..

char형은 임베디드에서 메모리 공간을 절약하기 위해서 int형 대신 많이 쓰인다. char형 변수에 값을 할당하고, 연산을 통해서 활용하기도 한다. 이 경험 때문에 헷갈리는 것 같다.

char형은 특수하다. 이름에서부터 알 수 있듯이 태생이 문자를 다루기 위해 만들어졌다. char형으로 입력과 출력을 하고자 하면 임베디드에서의 활용과 달라진다. 우선 키보드로 입력을 하면 무조건 문자로 인식된다. 1을 입력하면 정수 1이 입력되는 것이 아니라 문자 1이 입력되어, 저장되는 값은 1의 아스키 코드에 해당하는 49이다. 반대로 char형 변수에 49를 할당하고 해당 변수를 출력하면 1이 출력된다.

내가 출력해서 확인해보고 잘 들어가 있다고 판단한 것은 눈으로 보기에는 0과 1이 출력되었기 때문이다.

입력받은 map[i][j] 값은 아래 코드에서 참 거짓 판별에 사용된다. 0은 아스키 코드값 48이기 때문에 0이든 1이든 참으로 해석된다. 올바른 연산을 하기위해 문자 0과 1을 정수 0, 1로 바꿔야 한다.

if (map[nextRow][nextCol]) dq.push_back({nextRow, nextCol, cnt + 1});

그래서 아래와 같이 문자열 다룰 때 흔히 나오는 스킬인 48을 빼주어서 해결할 수 있다.

for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= m; ++j) {
        cin >> map[i][j];
        map[i][j] -= 48;
    }
}

---

풀이 코드

#include <iostream>
#include <deque>
using namespace std;
char map[101][101];
int visit[101][101];
int dx[4] = {0, 1, 0, -1};
int dy[4] = {-1, 0, 1, 0};

struct Info {
    int x, y, cnt;
};

int main()
{
    int m, n;
    cin >> m >> n;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            cin >> map[i][j];
            map[i][j] -= 48;
        }
    }

    deque<Info> dq;
    dq.push_back({1, 1, 0});
    visit[1][1] = 1;
    while (!dq.empty()) {
        Info cur = dq.front(); dq.pop_front();
        int row = cur.x;
        int col = cur.y;
        int cnt = cur.cnt;
        if (row == n && col == m) {
            cout << cnt << endl;
            break;
        }
        for (int i = 0; i < 4; ++i) {
            int nextRow = row + dx[i]; 
            int nextCol = col + dy[i];
            if (nextRow < 1 || nextRow > n || nextCol < 1 || nextCol > m) continue;
            if (visit[nextRow][nextCol]) continue;
            
            visit[nextRow][nextCol] = 1;
            if (map[nextRow][nextCol]) dq.push_back({nextRow, nextCol, cnt + 1});
            else dq.push_front({nextRow, nextCol, cnt});
        }
    }
    return 0;
}