[5558번] 치~즈

문제 출처 :

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

알고리즘 분석 :

문제 해결에 필요한 사항

1. BFS

기본 BFS에 memset을 하며 각 숫자를 계속 찾아가는 방식을 취하면 된다.

w,h의 값이 더 커지거나 memset을 하기 싫다면 visit를 int형으로 바꾸어 visitCnt를 이용해보자.

시간적인 측면에서 많은 이득을 볼 것이다.(대신 bool->int형으로 바뀌기에 메모리는 더 많이 먹게된다.)

소스 코드 : 

#include <iostream>
#include <cstdio>
#include <queue>
#include <memory.h>
 
using namespace std;
 
typedef pair<int, int> pii;
typedef pair<char, int> pci;
 
char arr[1003][1003];
bool visit[1003][1003];
 
int dy[4] = { 1,0,-1,0 };
int dx[4] = { 0,1,0,-1 };
 
int main()
{
    int w, h, n;
    int sx, sy;
    scanf("%d %d %d", &w, &h, &n);
 
    for (int i = 0; i < w; i++)
        for (int j = 0; j < h; j++)
        {
            scanf(" %c", &arr[i][j]);
            if (arr[i][j] == 'S')
                sy = i, sx = j;
        }
 
 
    queue<pair<pci, pii> > q;
 
    q.push({ {'1', 0}, {sy, sx} });
 
    while (!q.empty())
    {
        int y = q.front().second.first;
        int x = q.front().second.second;
        char cnt = q.front().first.first;
        int num = q.front().first.second;
 
        q.pop();
        
        if (visit[y][x])
            continue;
 
        visit[y][x] = true;
 
        if (arr[y][x] == cnt)
        {
            while (!q.empty())
                q.pop();
 
            q.push({ {cnt + 1, num}, {y,x} });
            memset(visit, false, sizeof(visit));
            
            if(cnt == n + '0')
            {
                printf("%d", num);
                return 0;
            }
        
            continue;
        }
 
        
        for (int i = 0; i < 4; i++)
        {
            int ny = y + dy[i];
            int nx = x + dx[i];
 
            if (!(0 <= ny && ny < w) || !(0 <= nx && nx < h) || visit[ny][nx] || arr[ny][nx] == 'X')
                continue;
 
            q.push({ {cnt, num + 1},{ny,nx} });
        }
 
    }
 
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>

#include <iostream>
#include <cstdio>
#include <queue>
 
using namespace std;
 
typedef pair<int, int> pii;
typedef pair<char, int> pci;
 
char arr[1003][1003];
int visit[1003][1003];
int visitCnt = 1;
 
int dy[4] = { 1,0,-1,0 };
int dx[4] = { 0,1,0,-1 };
 
int main()
{
    int w, h, n;
    int sx, sy;
    scanf("%d %d %d", &w, &h, &n);
 
    for (int i = 0; i < w; i++)
        for (int j = 0; j < h; j++)
        {
            scanf(" %c", &arr[i][j]);
            if (arr[i][j] == 'S')
                sy = i, sx = j;
        }
 
 
    queue<pair<pci, pii> > q;
 
    q.push({ {'1', 0}, {sy, sx} });
 
    while (!q.empty())
    {
        int y = q.front().second.first;
        int x = q.front().second.second;
        char cnt = q.front().first.first;
        int num = q.front().first.second;
 
        q.pop();
        
        if (visit[y][x] == visitCnt)
            continue;
 
        visit[y][x] = visitCnt;
 
        if (arr[y][x] == cnt)
        {
            while (!q.empty())
                q.pop();
 
            q.push({ {cnt + 1, num}, {y,x} });
            visitCnt++;
            
            if(cnt == n + '0')
            {
                printf("%d", num);
                return 0;
            }
        
            continue;
        }
 
        
        for (int i = 0; i < 4; i++)
        {
            int ny = y + dy[i];
            int nx = x + dx[i];
 
            if (!(0 <= ny && ny < w) || !(0 <= nx && nx < h) || visit[ny][nx] == visitCnt || arr[ny][nx] == 'X')
                continue;
 
            q.push({ {cnt, num + 1},{ny,nx} });
        }
 
    }
 
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>