백준 9328 열쇠

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

9328번: 열쇠

#include<stdio.h>
#include<queue>
#include<vector>
#define NSIZE 104
#define MSIZE 104
using namespace std;
char input[NSIZE][MSIZE];
int N, M;
int ret;
int dy[] = { 0,1,0,-1 };
int dx[] = { 1,0,-1,0 };
struct Data {
    int y, x;
};
vector<Data>pos;
int Alpha[26];
int chk[NSIZE][MSIZE];
void init() {
    ret = 0;
    pos.clear();
    memset(Alpha, 0, sizeof(Alpha));
    memset(input, 0, sizeof(input));
    memset(chk, 0, sizeof(chk));
 
    scanf("%d %d", &N, &M);
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= M; j++) {
            scanf(" %1c", &input[i][j]);
        }
    }
    char arr[26];
 
    scanf("%s", arr);
    if (arr[0] == '0')return;
    for (int i = 0; arr[i] != NULL; i++) {
        Alpha[arr[i] - 'a'] = 1;
    }
}
void bfs() {
        queue<Data>q;
        queue<Data>door[26];
        memset(chk, 0, sizeof(chk));
        q.push({ 0,0 }); chk[0][0] = 1;
        while (!q.empty()) {
            Data c = q.front(); q.pop();
            for (int dir = 0; dir < 4; dir++) {
                Data n;
                n.y = c.y + dy[dir];
                n.x = c.x + dx[dir];
                if (0 <= n.y&&n.y <= N + 1 && 0 <= n.x&&n.x <= M + 1) {
 
                    if (input[n.y][n.x] != '*'&&chk[n.y][n.x] == 0) {
                        chk[n.y][n.x] = 1;
                        if ('A' <= input[n.y][n.x] && input[n.y][n.x] <= 'Z') {
                            if (Alpha[input[n.y][n.x] - 'A'])q.push({ n.y,n.x });
                            else door[input[n.y][n.x] - 'A'].push({ n.y,n.x });
                        }
 
                        else if ('a' <= input[n.y][n.x] && input[n.y][n.x] <= 'z') {
                            q.push({ n.y,n.x });
                            if (!Alpha[input[n.y][n.x] - 'a']) {
                                Alpha[input[n.y][n.x] - 'a'] = 1;
                                while (!door[input[n.y][n.x] - 'a'].empty()) {
                                    q.push({ door[input[n.y][n.x] - 'a'].front() }); door[input[n.y][n.x] - 'a'].pop();
                                }
                            }
                        }
                        else {
                            q.push({ n.y,n.x });
                            if (input[n.y][n.x] == '$')ret++;
                        }
                    }
                }
            }
        }
}
int main(void) {
    int T = 0;
    scanf("%d", &T);
    for (int t = 1; t <= T; ++t) {
        //printf("%d", ret);
 
        init();
        bfs();
        printf("%d\n", ret);
    }
    return 0;
}

Alpha[input[n.y][n.x] - 'A'

Alpha[input[n.y][n.x] - 'a'

이렇게 하신걸 볼수 있는데 이것은 0인 인덱스 를 만들기위함 0인 인덱스보다는 숫자인 인덱스로 생각하겠다가 맞는

표현 같네요.

알파벳을 만나면 대문자는  A가 65 이므로  B는 아스키코드가66 이렇게 한개씩증가합니다.

그럼 이걸 배열 인덱스로 그냥 쓴다 생각해봅시다

그럼  arr[A] == arr[65] 랑 같다고 생각하시면 됩니다. 그럼 0부터 64인 공간은 낭비죠?

그렇지 않기위해서 0으로 만들어주기위해 즉 0 부터 1 ~... 이렇게 받기위해 -'A'를 빼서쓰는것이죠,

 소문자 a도 같은 의미입니다.

저는 처음 C언어 소스를 봤을때 저렇게 짠사람은 비상하다 정말 신적인 존재라 생각을 했었을때가 있는데 그냥 쓰시다 

보면 당연히 저렇게 해야구나 체득하시게 되는 날있습니다. 제가 저것을 안다고해서 알고리즘 마스터는 아니지만 

처음 에는 그렇게 생각이 들더군요 .

 

열쇠를 찾았을때 그때 문 위치부터 시작하게 왜 큐에 넣는지 그림으로 설명하자면 이렇습니다.

저렇게 큐배열에 이미 상근이가 문앞에 있는경우를 저장해놓고 문을 열 수 있는 열쇠가 생기면 그 경우도 상근이가

이동을 해야하므로 저렇게 열쇠를 따고 그것을 큐에 넣어주면 그위치에서 상하좌우 또 갈 수있게 해주는것이죠.

 

저렇게 보시니 쉽나요? 사실 제설명이 완벽한 소스가 아니라 어려우실수 있지만 이렇게도 

풀수 있으니 한번 도전해보세요.

오늘은 여기까지이고 언제나 즐거운 코딩하세요.