#문제

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

 

#작성 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include <iostream>
#include <cstdio>
#include <queue>
using namespace std;
 
int N, M;
int map[101][101];            // 인덱스 1~100 사용(총 100칸)
int visit[101][101];            // 방문 체크. 여기까지 오는데 몇 칸 걸렸는가 
int v[4][2= {{1,0}, {0,1}, {-1,0}, {0,-1}};
queue< pair<intint> > q;
 
void input(){
    scanf("%d %d"&N, &M);
    for(int i=1; i<=N; i++)
        for(int j=1; j<=M; j++)
            scanf("%1d"&map[i][j]);
}
 
// 범위 내에 존재하는지 체크 
bool isIn(int x, int y){
    return x>0&&x<=N&&y>0&&y<=M;
}
 
void solve(int i, int j){
    map[i][j] = 9;
    visit[i][j]=1;                    // 이 지점에는 방문했다는 뜻! 
    q.push(make_pair(i, j));
    
    while(!q.empty()){
        int x=q.front().first;
        int y=q.front().second;
        q.pop();
        
        for(int k=0; k<4; k++){
            // 상하좌우를 체크 
            int nx = x+v[k][0];
            int ny = y+v[k][1];
            // 미로 내에 존재하고, 길이라면 방문한다. 
            if( isIn(nx, ny)&&map[nx][ny]==1 ){
                visit[nx][ny] = visit[x][y]+1;    // 이 지점에 방문했다는 뜻! 
                map[nx][ny] = 9;
// 이 지점에 다시 방문하지 않도록 0과 1이 아닌 수로 바꿔준다
                q.push(make_pair(nx, ny));                                
            }
        }
    }
}
 
int main(){
    input();
    solve(1,1);
    printf("%d\n", visit[N][M]);
    return 0;
}
cs

 

##

visit 배열은 (1,1)에서 출발해서 몇 번째만에 해당 칸에 도착했는지를 저장하는 배열이다.

bfs를 이용해 연결되어있는 모든 1을 탐색하면서 그 칸까지 몇 번째만에 도착했는지를 세서, (N, M)에 얼마가 저장되어있는지를 출력하면 된다.

 

이전에 풀었던 2667 단지번호붙이기, 1012 유기농배추 문제와 거의 똑같이 풀었다.

차이점은 visit 배열.

 

#191206 REVIEW

void input()  으로 입력받는다.

bool isIn()    지도 범위 내에 좌표가 존재하는지 체크

void solve(int i, int j){

      1. 시작지점에 방문. map[i][j]=9, visit[i][j]=1 저장. visit배열에는 시작지점과 도착지점을 포함해서 여기까지 오는데 걸렸는지를 저장하는 배열이다.

      2. 시작지점을 큐에 넣는다.

      3. 큐가 때까지 반복한다.

            1. q.push({nx, ny});

            2. visit[nx][ny] = visit[x][y]+1;      nx,ny x,y에서 상하좌우위치에 있으므로 1 차이난다. x,y + 1칸을 저장한다.

            3. map[nx][ny] =9; 저장해서 다시 방문하지 않도록 한다.

                  1. 현재 위치를 x, y, 저장하고, q.pop()실행.

                  2. 현재 위치의 , , , 우를 체크한다. 미로의 범위 내에 존재하고, 길이라면 방문한다.

            4. visit[N][M] 출력한다. (N,M 도착지점임)

}

'BOJ' 카테고리의 다른 글

BOJ 7569번 :: 토마토 (2)  (0) 2019.12.06
BOJ 7576번 :: 토마토  (0) 2019.12.06
BOJ 1753번 :: 최단경로  (0) 2019.12.05
BOJ 1012번 :: 유기농 배추  (0) 2019.12.05
BOJ 11053번 :: 가장 긴 증가하는 부분수열  (0) 2019.12.05

+ Recent posts