개발 블로그

문제 링크 : www.acmicpc.net/problem/16927

문제

크기가 N×M인 배열이 있을 때, 배열을 돌려보려고 한다. 배열은 다음과 같이 반시계 방향으로 돌려야 한다.

예를 들어, 아래와 같은 배열을 2번 회전시키면 다음과 같이 변하게 된다.

배열과 정수 R이 주어졌을 때, 배열을 R번 회전시킨 결과를 구해보자.

입력

첫째 줄에 배열의 크기 N, M과 수행해야 하는 회전의 수 R이 주어진다.

둘째 줄부터 N개의 줄에 배열 A의 원소 Aij가 주어진다.

출력

입력으로 주어진 배열을 R번 회전시킨 결과를 출력한다.

제한

• 2 ≤ N, M ≤ 300
• 1 ≤ R ≤ 10^9
• min(N, M) mod 2 = 0
• 1 ≤ Aij ≤ 108

접근 방법

nanyoungkim.tistory.com/78

문제와 동일한데, 조건 하나가 다르다. R의 범위가 1000에서 10^9 까지 늘어났다는 것이다. 

예를 들어보자.

여기서 map[0][0]이 1번 전진하면 map[1][0]으로 간다. 그런데 1번 전진이 아니라 13번, 25번 전진해도 map[1][0]으로 간다. 

즉,

1 mod 12

13 mod 12

25 mod 12

는 모두 1임을 알 수 있는데, 여기서 modulus 12는 가장 바깥쪽 박스의 칸 수가 된다. 이는 2*N + 2*M -4 로 구할 수 있다. (-4는 각 모서리의 수들이 반복돼서 더해준 것을 뺀 것이다.)

박스가 하나씩 안 쪽으로 들어갈 때마다 가로, 세로의 길이는 각각 2씩 감소하는 것을 알 수 있다.

배열 돌리기 1번에서는 "각 박스에 대해 1칸 전진" 을 R번 반복 했다면, 

배열 돌리기 2번에서는 "박스 한개에 대해 R번 전진" 을 박스 개수만큼 반복해줬다.

결론은 박스 개수만큼 반복하는데, 한 박스마다 회전할 수를 R이 아닌 "R mod 박스칸수" 로 지정해서 R이 10^9처럼 큰 수가 들어와도 효율적으로 돌아갈 수 있게 했다.

//21.03.10
//next가 배열 범위 넘어가면 dr[],dc[]의 인덱스 증가
//top, right, bottom, left 순서로 칸 이동시킴
//(시계 반대방향으로 전진해야하므로 dr,dc의 인덱스는 오,아,왼,위 순서)

#include <iostream>
#include <algorithm>


using namespace std;

int map[301][301];
int N,M,R;

//오, 아, 왼, 위
int dr[4] = {0,1,0,-1};
int dc[4] = {1,0,-1,0};

void rotate(int start, int len){
    
    int r = R%len;			//len은 박스의 총 칸 수
    for(int i = 0; i<r; i++){   //r칸 전진
        
        int startVal = map[start][start];
        int r = start;
        int c = start;
        
        int k = 0;
        while(k<4){
            
            int nr = r + dr[k];     //map[nr][nc]는 옮길 대상임 (map[r][c]로 옮겨야 함)
            int nc = c + dc[k];
            
            if(nr==start && nc==start) break;
            if(start<=nr && nr<N-start && start<=nc && nc<M-start){
                
                //차례로 시계 반대방향으로 옮김
                map[r][c] = map[nr][nc];
                r = nr;
                c = nc;
                
            }
            else{       //다음에 옮길 칸이 배열 범위 넘어가버리면 해당 라인은 다 옮긴거라서 k 증가
                k++;
            }
        }
        map[start+1][start] = startVal; //처음에 시작지점 빼놨던거 마지막에 빈 자리에 넣어줌.
        
    }

    
}


int main(){
    
    cin >> N >> M >> R;
        
    for(int i = 0; i<N; i++){
        for(int j = 0; j<M; j++){
            cin >> map[i][j];
        }
    }
    
    int cnt = min(N,M)/2;       //  박스 수


    int n=N, m=M;
    
    for(int i = 0; i<cnt; i++){ //반복문 1번에,  박스 1개가 R만큼 전진함
            //시작 지점
        rotate(i, 2*n + 2*m -4);
        n-=2;	//박스 안으로 들어갈때마다 가로,세로 2씩 줄어듦.
        m-=2;
        
    }
    
    
    
    
    
    for(int i = 0; i<N; i++){
        for(int j = 0; j<M; j++){
            cout << map[i][j] << " ";
        }cout <<"\n";
    }
    
    
    
    return 0;
}

문제 링크 : www.acmicpc.net/problem/16926

문제

크기가 N×M인 배열이 있을 때, 배열을 돌려보려고 한다. 배열은 다음과 같이 반시계 방향으로 돌려야 한다.

예를 들어, 아래와 같은 배열을 2번 회전시키면 다음과 같이 변하게 된다.

배열과 정수 R이 주어졌을 때, 배열을 R번 회전시킨 결과를 구해보자.

입력

첫째 줄에 배열의 크기 N, M과 수행해야 하는 회전의 수 R이 주어진다.

둘째 줄부터 N개의 줄에 배열 A의 원소 Aij가 주어진다.

출력

입력으로 주어진 배열을 R번 회전시킨 결과를 출력한다.

제한

• 2 ≤ N, M ≤ 300
• 1 ≤ R ≤ 1,000
• min(N, M) mod 2 = 0
• 1 ≤ Aij ≤ 108

접근 방법

모든 박스에 대해서 시계 반대 방향으로 요소를 1칸씩 이동시키며, 이를 R번 반복한다.

여기서 박스는

이렇게 두개이다.

박스의 시작지점은 map[0][0] -> map[1][1] -> map[2][2]...... map[박스수][박스수] 이런 순으로 가게 된다.

박스의 개수는 min(N,M) / 2 개이며 문제의 조건에서 min(N,M) mod 2=0이라고 했으므로 둘 중하나는 짝수이고 (3x3) 이나 (5x5) 같은 경우는 고려하지 않아도 된다.

먼저 각 박스에 대해서 1칸 시계 반대방향으로 이동하는 걸 생각해보자.  1) map[0][0]을 시작지점으로 잡는다.

2) Top : 왼쪽으로 이동한다. 

next 칸이 now칸의 오른쪽에 있으므로 dr[],dc[]는 오른쪽.

3) Right : 위쪽으로 이동한다.

next 칸이 now칸의 아래쪽에 있으므로 dr[],dc[]는 아래.

4) Bottom : 오른쪽으로 이동한다.

next 칸이 now칸의 왼쪽 있으므로 dr[],dc[]는 왼쪽.

5) Left : 아래쪽으로 이동한다.

next 칸이 now칸의 위에 있으므로 dr[],dc[]는 위.

전체적인 로직은 위와 같으며, next 칸이 시작점으로 돌아왔을 때 반복을 멈추고, 남은 자리에 1)에서 저장했던 값을 넣어주면 된다.

//21.03.10
//next가 배열 범위 넘어가면 dr[],dc[]의 인덱스 증가
//top, right, bottom, left 순서로 칸 이동시킴
//(시계 반대방향으로 전진해야하므로 dr,dc의 인덱스는 오,아,왼,위 순서)

#include <iostream>
#include <algorithm>


using namespace std;

int map[301][301];
int N,M,R;

//오, 아, 왼, 위
int dr[4] = {0,1,0,-1};
int dc[4] = {1,0,-1,0};

void rotate(int box){
    
    for(int i=0; i<box; i++){   //박스수만큼 반복(1칸 전진)(시작점은 start, start+1, start+2..)
        int startVal = map[i][i];       //각 박스 시작은 [0][0] -> [1][1] -> [2][2]...
        int r = i;
        int c = i;
        
        int k = 0;
        while(k<4){
            
            int nr = r + dr[k];     //map[nr][nc]는 옮길 대상임 (map[r][c]로 옮겨야 함)
            int nc = c + dc[k];
            
            if(nr==i && nc==i) break;
            if(i<=nr && nr<N-i && i<=nc && nc<M-i){
                
                //차례로 시계 반대방향으로 옮김
                map[r][c] = map[nr][nc];
                r = nr;
                c = nc;
                
            }
            else{       //다음에 옮길 칸이 배열 범위 넘어가버리면 해당 라인은 다 옮긴거라서 k 증가
                k++;
            }
        }
        map[i+1][i] = startVal; //처음에 시작지점 빼놨던거 마지막에 빈 자리에 넣어줌.
     
    }
 
    
}


int main(){
    
    cin >> N >> M >> R;
        
    for(int i = 0; i<N; i++){
        for(int j = 0; j<M; j++){
            cin >> map[i][j];
        }
    }
    
    int cnt = min(N,M)/2;       //  박스 수
    
    for(int i = 0; i<R; i++){       //반복문 한번에 1칸 전진하는것. 총 R칸 전진
        rotate(cnt);
    }


    for(int i = 0; i<N; i++){
        for(int j = 0; j<M; j++){
            cout << map[i][j] << " ";
        }cout <<"\n";
    }
    
    
    
    return 0;
}

참고 : 4ngeunlee.tistory.com/219

문제 링크 : www.acmicpc.net/problem/16931

문제

크기가 N×M인 종이가 있고, 종이는 1×1크기의 칸으로 나누어져 있다. 이 종이의 각 칸 위에 1×1×1 크기의 정육면체를 놓아 3차원 도형을 만들었다.

종이의 각 칸에 놓인 정육면체의 개수가 주어졌을 때, 이 도형의 겉넓이를 구하는 프로그램을 작성하시오.

위의 그림은 3×3 크기의 종이 위에 정육면체를 놓은 것이고, 겉넓이는 60이다.

입력

첫째 줄에 종이의 크기 N, M이 주어진다. 둘째 줄부터 N개의 줄에는 종이의 각 칸에 놓인 정육면체의 수가 주어진다.

출력

첫째 줄에 도형의 겉넓이를 출력한다.

접근 방법

각 배열 칸에 대해 옆면 4개의 겉넓이를 구하고 마지막에 위(N*M)넓이와 아래(N*M)넓이를 더해줬다.

각 배열 칸에 대한 옆면의 넓이 4개를 구하는게 관건인데, 이는 인접한 배열칸의 높이와 현재 위치칸의 높이의 차를 이용해서 구할 수 있다.

1) 현재칸 높이 >= 인접한 칸 높이 -> 가려지지 않은 부분의 높이는 (현재-인접)

2) 현재칸 높이 =< 인접한 칸 높이 -> 다 가려져 버려서 높이는 0

이때 주의할 점은 가장자리 즉 가장 바깥쪽 옆면의 넓이인데, 이는 인접한 칸의 높이가 0이라고 생각하면 된다. 

만약 N=4, M=4이면

o 표시한 곳에 입력받은 숫자를 저장하고

그 주위로는 0을 저장해서 높이를 0으로 표시하면 쉽게 계산할 수 있다.

#include <iostream>


using namespace std;

int arr[102][102];			//가장 자리 처리를 위해서 

//위 오 아 왼
int dr[4] = {-1,0,1,0};
int dc[4] = {0,1,0,-1};


int main(){
    
    int ans = 0;
    
    int N,M;
    cin>>N>>M;
    
    for(int i = 0; i<N+2; i++){		//가장 자리를 0으로 설정하기 위한 범위
        for(int j=0; j<M+2; j++){
            arr[i][j] = 0;
        }
    }
    
    for(int i = 1; i<=N; i++){			//가장 자리 빼고 안쪽에 숫자 입력 받음
        for(int j=1; j<=M; j++){
            cin>>arr[i][j];
        }
    }
    
    for(int r = 1; r<=N; r++){
        for(int c=1; c<=M; c++){
            
            for(int k = 0; k<4; k++){
                int nr = r+dr[k];
                int nc = c+dc[k];
                
                if(arr[r][c]>=arr[nr][nc]){			//현재 위치가 더 커서 위로 나올 때만 더함
                    ans+=arr[r][c] - arr[nr][nc];
                }
            }
            
            
        }
    }
    
    //위, 아래
    ans+=2*(N*M);
    cout << ans;
    
    return 0;
}

문제 링크 : www.acmicpc.net/problem/13549

문제

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 0초 후에 2*X의 위치로 이동하게 된다.

수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.

입력

첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다.

출력

수빈이가 동생을 찾는 가장 빠른 시간을 출력한다.

접근 방법

숨바꼭질 4 문제(nanyoungkim.tistory.com/75)와 비슷했지만 순간이동은 0초, 걷는건 1초로 가중치가 달랐기 때문에 덱을 이용했다.

순간이동은 0초가 걸리니까 앞에서 push 하고,

걷는건 1초가 걸리니까 뒤에서 push 했다.

(덱에는 pair<int 시간, int 위치> 를 저장했다. -> 시간에 따른 우선순위를 위해 첫번째 요소에 시간을 저장한 것임.)

주의할 점

아무 생각 없이 숨바꼭질4 문제와 같이 if 조건문 순서를 "뒤->앞->순간이동" 으로 해서 계속 7%에서 '틀렸습니다' 메세지가 출력됐다. push_front(), push_back()으로 구분을 해줬더라도 순간이동이 뒤/앞 이동보다 더 먼저 push 되어야한다!!

#include <iostream>
#include <deque>
#include <utility>

using namespace std;

int N, K;
int visited[100001] = {0};

int ans=0;

void BFS(){
    
    deque<pair<int,int>> que;
    que.push_back(make_pair(0,N));
    visited[N] = 1;
    
    while(!que.empty()){
        int nowTime = que.front().first;
        int nowLoc = que.front().second;
        que.pop_front();
        
        if(nowLoc==K){
            ans = nowTime;
            return;
        }
        
        //순간이동 -> 앞/뒤 이동보다 먼저 써줘야한다.
        if(!visited[2*nowLoc] && 0<=2*nowLoc && 2*nowLoc<=100000){
            visited[2*nowLoc] = 1;
            que.push_front(make_pair(nowTime, 2*nowLoc));
        }
        //뒤로 이동
        if(!visited[nowLoc-1] && 0<=nowLoc-1 && nowLoc-1<=100000){
            visited[nowLoc-1] = 1;
            que.push_back(make_pair(nowTime+1,nowLoc-1));
        }//앞으로 이동
        if(!visited[nowLoc+1] && 0<=nowLoc+1 && nowLoc+1<=100000){
            visited[nowLoc+1] = 1;
            que.push_back(make_pair(nowTime+1, nowLoc+1));

        }
    }
}


int main(){
    
    cin >> N >> K;
    BFS();
    cout << ans ;
    
    return 0;
}

문제 링크 : www.acmicpc.net/problem/13913

문제

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다.

수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.

입력

첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다.

출력

첫째 줄에 수빈이가 동생을 찾는 가장 빠른 시간을 출력한다.

둘째 줄에 어떻게 이동해야 하는지 공백으로 구분해 출력한다.

접근 방법

BFS로 한 스템씩 나아가면서 visited[]에 직전에 지났던 위치를 저장한다. 

visited[]는 처음에 시작점을 제외하고 -1로 초기화 시켰기 때문에 위치를 지정하면 동시에 방문여부도 체크할 수 있다.

stop 조건에 걸리면 visited[] 를 거꾸로 타고 올라가면서 지나온 자리를 resVec에 push 한다.

그리고 main()에서 resVec을 거꾸로 출력한다.

#include <iostream>
#include <queue>
#include <cstring>
#include <vector>

using namespace std;

int N, K;
int visited[100001];
queue<int> que;
vector<int> resVec;

void BFS(){
    
    que.push(N);
    
    while(!que.empty()){
        
        int now = que.front();
        que.pop();
        
        if(now==K){
            resVec.push_back(now);
            while(visited[now]!=100001){		   //처음 시작점까지 갈 때 까지
                resVec.push_back(visited[now]);   //거꾸로 타고 올라가면서 지나온 자리 push
                now = visited[now];
            }
            return;
        }
        
        
        if(visited[now-1]==-1 && 0<=now-1 && now-1<=100000){	//방문체크 and 범위체크
            visited[now-1] = now;		//바로 직전에 지나온 자리 저장
            que.push(now-1);			
        }
        if(visited[now+1]==-1 && 0<=now+1 && now+1<=100000){
            visited[now+1] = now;
            que.push(now+1);
        }
        if(visited[2*now]==-1 && 0<=2*now && 2*now <= 100000){
            visited[2*now] = now;
            que.push(2*now);
        }
    } 
}

int main(){
   
    cin >> N >> K;
    memset(visited, -1, sizeof(visited));
    visited[N] = 100001;		//시작 지점 체크를 위함
    
    BFS();
    cout << resVec.size()-1 << "\n";
    
    for(int i = resVec.size()-1; i>=0; i--){
        printf("%d ", resVec[i]);
    }
    
    return 0;
}

문제 링크 : www.acmicpc.net/problem/14226

문제

영선이는 매우 기쁘기 때문에, 효빈이에게 스마일 이모티콘을 S개 보내려고 한다.

영선이는 이미 화면에 이모티콘 1개를 입력했다. 이제, 다음과 같은 3가지 연산만 사용해서 이모티콘을 S개 만들어 보려고 한다.

1. 화면에 있는 이모티콘을 모두 복사해서 클립보드에 저장한다.
2. 클립보드에 있는 모든 이모티콘을 화면에 붙여넣기 한다.
3. 화면에 있는 이모티콘 중 하나를 삭제한다.

모든 연산은 1초가 걸린다. 또, 클립보드에 이모티콘을 복사하면 이전에 클립보드에 있던 내용은 덮어쓰기가 된다. 클립보드가 비어있는 상태에는 붙여넣기를 할 수 없으며, 일부만 클립보드에 복사할 수는 없다. 또한, 클립보드에 있는 이모티콘 중 일부를 삭제할 수 없다. 화면에 이모티콘을 붙여넣기 하면, 클립보드에 있는 이모티콘의 개수가 화면에 추가된다.

영선이가 S개의 이모티콘을 화면에 만드는데 걸리는 시간의 최솟값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 S (2 ≤ S ≤ 1000) 가 주어진다.

출력

첫째 줄에 이모티콘을 S개 만들기 위해 필요한 시간의 최솟값을 출력한다.

접근 방법

처음 시작 조건(이모티콘 1개, 시간 0초, 클립보드 0개)에서 시작해서 각각 연산을 수행한 뒤 상태를 Queue에 push 한다.

여기서 주의할 점은 방문 여부를 체크하는 visit 배열이 이차원 배열이라는 것이다.

visit[i][j] 는 화면에 i개 이모티콘이 있고 클립보드에 j개 이모티콘이 있는 상태이다. 

처음에  '시간이 더 나중인게 이모티콘 글자 수가 더 큰 경우' 에는 ?

이라는 의문이 들었는데, 

whlie문 한 번 돌 때마다

if(s==S)인지 체크하고 / 1초씩 순차적으로 증가하기 때문에

if(s==S)이 만족해서 반복문이 멈출 때가 바로 시간의 최소값이다. 

#include <iostream>
#include <queue>
#include <utility>
#include <vector>
#include <algorithm>

using namespace std;

int S;
int visit[1001][1001];
int ans;

void BFS(){
    //임티개수,              초, 클립보드 안의 수
    queue<pair<int, pair<int,int>>> que;
    que.push(make_pair(1, make_pair(0,0)));
    visit[1][0] = 1;

    while(!que.empty()){
          
        int s = que.front().first;
        int sec = que.front().second.first;
        int clip = que.front().second.second;
        que.pop();
        
       // cout << s<<"개 / " << sec<<"초  /  " << clip<<"클립보드\n";
       
        if(s==S) {
            ans = sec;
            return;
        }
        
        if(s>0 && s<=1000){
            //복사
            if(visit[s][s]==0){
                visit[s][s] = 1;
                que.push(make_pair(s, make_pair(sec+1, s)));
            }
            
            //하나 삭제
            if(visit[s-1][clip] == 0){
                visit[s-1][clip] = 1;
                que.push(make_pair(s-1, make_pair(sec+1, clip)));
            }
        }
        
        //붙여넣기
        if(clip>0 && s+clip<=1000){
            if(visit[s+clip][clip]==0){
                visit[s+clip][clip] = 1;
                que.push(make_pair(s+clip, make_pair(sec+1, clip)));
            }
        }
    }
}


int main(){

    cin >> S;

    for(int i = 0; i<=1000; i++){
        for(int j = 0; j<=1000; j++){
            visit[i][j] = 0;
        }
    }
    
    BFS();
    cout << ans;

    return 0;
}

문제 링크 : www.acmicpc.net/problem/1261

문제

알고스팟 운영진이 모두 미로에 갇혔다. 미로는 N*M 크기이며, 총 1*1크기의 방으로 이루어져 있다. 미로는 빈 방 또는 벽으로 이루어져 있고, 빈 방은 자유롭게 다닐 수 있지만, 벽은 부수지 않으면 이동할 수 없다.

알고스팟 운영진은 여러명이지만, 항상 모두 같은 방에 있어야 한다. 즉, 여러 명이 다른 방에 있을 수는 없다. 어떤 방에서 이동할 수 있는 방은 상하좌우로 인접한 빈 방이다. 즉, 현재 운영진이 (x, y)에 있을 때, 이동할 수 있는 방은 (x+1, y), (x, y+1), (x-1, y), (x, y-1) 이다. 단, 미로의 밖으로 이동 할 수는 없다.

벽은 평소에는 이동할 수 없지만, 알고스팟의 무기 AOJ를 이용해 벽을 부수어 버릴 수 있다. 벽을 부수면, 빈 방과 동일한 방으로 변한다.

만약 이 문제가 알고스팟에 있다면, 운영진들은 궁극의 무기 sudo를 이용해 벽을 한 번에 다 없애버릴 수 있지만, 안타깝게도 이 문제는 Baekjoon Online Judge에 수록되어 있기 때문에, sudo를 사용할 수 없다.

현재 (1, 1)에 있는 알고스팟 운영진이 (N, M)으로 이동하려면 벽을 최소 몇 개 부수어야 하는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 미로의 크기를 나타내는 가로 크기 M, 세로 크기 N (1 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 미로의 상태를 나타내는 숫자 0과 1이 주어진다. 0은 빈 방을 의미하고, 1은 벽을 의미한다.

(1, 1)과 (N, M)은 항상 뚫려있다.

출력

첫째 줄에 알고스팟 운영진이 (N, M)으로 이동하기 위해 벽을 최소 몇 개 부수어야 하는지 출력한다.

접근 방법

visit[][]로 방문 여부를 체크해야하나 싶었는데, 그렇게 하면 나중에 방문한 경우가 더 적게 벽을 부신 경우가 될 수 있기 때문에 다른 방법을 고려해야 했다.

즉, 다음 방문할 칸이 벽이던 방이던, 갱신 조건(더 적게 벽을 부신 경우)을 만족할 경우에만 Queue에 push 해주면 된다. 그러면 마지막에 cntWall[N][M]에서 상하좌우로 탐색을 할 때 범위체크에서 우/하 방향이 걸러지고 상/좌의 경우에는 갱신조건을 만족하지 못하므로(cntWall가 같으므로) 더이상 Queue 에 Push 하지 않고 while문을 벗어나게 된다. 

(while문 안에 if 조건문으로 탈출 조건을 따로 안 써줘도 된다.)

주의할 점

처음에 메모리 초과가 난 이유가 Queue에 너무 많은 원소가 들어가서였다. 그 코드에서는 범위 체크만 통과하면 바로 Queue에 next 칸을 push 했었다. 

수정된 아래의 코드처럼 갱신 조건을 만족할 때만 Queue 에 push 해주면 메모리초과가 안 뜬다.

#include <iostream>
#include <utility>
#include <queue>

using namespace std;

#define MAX 101

int N,M;
int map[MAX][MAX];
queue<pair<int,int>> que;

int cntWall[MAX][MAX];

//위 오 아 왼
int dr[4] = {-1, 0, 1, 0};
int dc[4] = {0, 1, 0, -1};

void BFS(){
    
    while(!que.empty()){

        int r = que.front().first;
        int c = que.front().second;
        que.pop();
        
        for(int i = 0; i<4; i++){
            int nr = r + dr[i];
            int nc = c + dc[i];
            
            if(nr<1 || nr>N || nc<1 || nc>M) continue;		//범위 체크
	
            if(map[nr][nc] == 1){		//다음 칸이 벽일 때
                
                if(cntWall[nr][nc] > cntWall[r][c]+1){		//갱신 조건
                    cntWall[nr][nc] =cntWall[r][c]+1;
                     que.push(make_pair(nr,nc));
                }
                
            }
            else{						//다음 칸이 방일 때
                if(cntWall[nr][nc]>cntWall[r][c]){			//갱신 조건
                    cntWall[nr][nc] = cntWall[r][c];
                    que.push(make_pair(nr,nc));
                }
            }
        }
    }
}

int main(){

    cin >> M >> N;
    string str;
    for(int i = 1; i<=N; i++){
        for(int j = 1; j<=M; j++){
            cntWall[i][j] = 1000;			//최대 값으로 초기 설정
        }
    }
    
    for(int i = 1; i<=N; i++){
        cin >> str;
        for(int j = 1; j<=str.length(); j++){
            map[i][j] = str[j-1]-'0';
        }
    }
    //입력받을 때 동일한 방법
    /* for(int i = 1; i<=N; i++){
        for(int j = 1; j<=M; j++){
            scanf( "%1d", &map[i][j] );
        }
    }*/
   
    
    que.push(make_pair(1,1));
    cntWall[1][1] = 0;          //항상 뚫려 있다고 했으므로 0으로 초기 설정 가능
    
    BFS();
    
    cout << cntWall[N][M];
   
    
    return 0;
}

• close() 함수 호출을 통해 일방적으로 connection을 종료하면 host 사이에 데이터가 정상적으로 도달하지 못한채 종료되는 경우가 발생할 수 있다.
• 소켓의 스트림은 한쪽 방향으로만 데이터의 이동이 가능하기 때문에 양방향 통신을 위해서는 두개의 스트림이 필요하다.
• host1의 출력 스트림은 host2의 입력 스트림으로, host 2의 출력 스트림은 host1의 입력 스트림으로 이어진다.

[우아한 종료를 위한 shoutdown 함수]

int shutdown(int sock, int howto);

• sock : 종료할 소켓의 파일 디스크립터 전달
• howto : 종료 방법에 대한 정보 전달

1. SHUT_RD : 입력 스트림 종료

2. SHUT_WR : 출력 스트림 종료

3. SHUT_RDWR : 입출력 스트림 종료

[file_client.c]

[file_client.c]

[터미널 실행 결과]

• “Thank you” : 클라이언트 -> 서버 (shutdown 함수 호출 후에 read 함수를 이용하여 클라이언트가 보낸 메세지를 받아왔다.