인프런 커뮤니티 질문&답변

안녕하세요 ㅎㅎ

잘 짜셨네요 ㅎㅎ

코드리뷰는 다음과 같습니다.

x, y가 바뀌었습니다.

            if(outOfBound(ny,nx) || visited[ny][nx] || isWall(ny,nx)) continue; 
            if(fmap[ny][nx] <= visited[y][x] + 1) continue; //이미 불이 있는 지역 
            q.push({ny,nx});
            visited[ny][nx] = visited[y][x] + 1;

그리고 outofbound부터 체크를 해야 합니다. 그래야 배열의 오버플로가 발생하지 않습니다.

전체 코드.

// Online C++ compiler to run C++ program online
#include <bits/stdc++.h>
using namespace std; 
// 입력의 첫째 줄에는 공백으로 구분된 두 정수 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1000 이다. R은 미로 행의 개수, C는 열의 개수이다.
typedef pair<int,int> pp; 
int R,C;
int visited[1004][1004]; 
char cmap[1004][1004]; 
int fmap[1004][1004]; 
int dx[4] = {0,0,1,-1}; 
int dy[4] = {-1,1,0,0};
//pp start; 
queue<pp> q; 
queue<pp> fq; 

bool outOfBound(int y, int x){
    return (y < 0 || x < 0 || y >= R || x >= C );
}

bool isExit(int y, int x){//탈출구 
    return (y == 0 || x == 0 || y == R - 1 || x == C -1); 
}

bool isWall(int y, int x){
    return cmap[y][x] == '#'; 
}

void input(){
    // 초기화 
    fill(&fmap[0][0],&fmap[0][0] + 1004 * 1004 , INT_MAX ); 
    cin >>R>>C;
    for(int i=0;i<R;i++)
    for(int j=0;j<C;j++){
        cin >> cmap[i][j];
        if(cmap[i][j] == 'F'){//fire then 
            fmap[i][j] = 1; 
            fq.push({i,j}); 
        }
        if(cmap[i][j] == 'J'){//출발 지점 
            visited[i][j] = 1;
            q.push({i,j}); 
        }
    } 
}

//bfs 
int solution(){
    int y,x; 
    int ny,nx; 
    //bfs fire
    while(!fq.empty()){
        tie(y,x) = fq.front(); 
        fq.pop(); 
        for(int i=0; i<4; i++){
            ny = y + dy[i]; 
            nx = x + dx[i]; 
            
            if( fmap[ny][nx] != INT_MAX ) continue; //visited  
            if(outOfBound(ny,nx) || isWall(ny,nx)) continue; 
            
            fq.push({ny,nx}); 
            fmap[ny][nx] = fmap[y][x] + 1; 
        } 
    }
    //bfs person 
    while(!q.empty()){
        tie(y,x) = q.front(); 
        q.pop(); 
        if(isExit(y,x)){
            return visited[y][x]; 
        }  
        for(int i=0; i<4; i++){
            ny = y + dy[i]; 
            nx = x + dx[i];
            if(outOfBound(ny,nx) || visited[ny][nx] || isWall(ny,nx)) continue; 
            if(fmap[ny][nx] <= visited[y][x] + 1) continue; //이미 불이 있는 지역 
            q.push({ny,nx});
            visited[ny][nx] = visited[y][x] + 1;
        }
    }
    return -1; 
}

//solve
void solve(){
    input(); 
    int result = solution();
    if(result == -1) cout << "IMPOSSIBLE"; 
    else cout << result; 
}

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

원본 반례 찾아보다가 시험 해본 케이슨데 해설지 답에서 걸러내지 못하는 것 같습니다.

>> 아닙니다. imposible이라고 잘뜹니다.

5 5

#####

#J#F#

##..#

#...#

#...#

IMPOSSIBLE

이렇게 잘 나오는 것을 볼 수 있습니다.

또 질문 있으시면 언제든지 질문 부탁드립니다.

좋은 수강평과 별점 5점은 제게 큰 힘이 됩니다. :)

감사합니다.

강사 큰돌 올림.