JArchive 프로그래밍 일기

문제

유기농 배추 백준 1012

"맞았습니다" 코드

#include <bits/stdc++.h>
#define X first
#define Y second
using namespace std;

// 1012 유기농 배추
int t, n, m, k, x, y;
int ground[52][52];
int vis[52][52];
int dx[] = {1, 0, -1, 0};
int dy[] = {0, 1, 0, -1};

bool checkrange(int i, int j){
  return (i >= 0 && i < n && j >= 0 && j < m );
}

void initground(){
  for(int i = 0; i < 52; i++) fill(ground[i], ground[i]+n, 0);
}

void initvis(){
  for(int i = 0; i < 52; i++) fill(vis[i], vis[i]+n, 0);
}

void bfs(int si, int sj){

  queue<pair<int,int>> qu;
  ground[si][sj] = 0;
  qu.push({si, sj});

  while(!qu.empty()){
    int cx = qu.front().X;
    int cy = qu.front().Y;
    qu.pop();

    for(int i = 0; i <4; i++){
      int nx = dx[i] + cx;
      int ny = dy[i] + cy;

      if(!checkrange(nx, ny) || !ground[nx][ny]) continue;
      ground[nx][ny] = 0; // 방문 표시
      qu.push({nx, ny});
    }
  }

}

int main(void) {
  ios::sync_with_stdio(0);
  cin.tie(0);

  cin >> t;

  while(t--){
    initground(); initvis();
    int answer = 0;

    cin >> m >> n >> k; // 가로길이, 세로길이, 배추개수

    while(k--){
      cin >> x >> y;  // 가로(열), 세로(행)
      ground[y][x] = 1;
    }

    for(int i = 0; i < n; i++){
      for(int j = 0; j < m; j++){
        if(ground[i][j] == 1){
          bfs(i, j);
          answer++;
        }
      }
    }
    cout << answer << '\n';
  }
  return 0;
}

리뷰

기본적인 bfs 문제였다.
2중 반복문에서 배추밭 1을 만나면, 인접한 배추밭을 모두 0으로 만든다.
bfs를 한 번 돌릴 때마다 배추밭 덩어리 개수를 셀 수 있으니까 answer를 1개씩 증가시킨다.

문제

나이트의 이동 백준 7562

"맞았습니다" 코드

#include <bits/stdc++.h>
#define X first
#define Y second
using namespace std;

int tc, n, curx, cury, targetx, targety;
int board[303][303];
bool vis[303][303] = {false};
int dx[] = {2, 1, 2, 1, -2, -1, -2, -1}; // 현재칸 기준 8방향으로 이동 가능 
int dy[] = {1, 2, -1, -2, 1, 2, -1, -2};

bool checkrange(int i, int j){
  return (i >= 0 && i < n && j >= 0 && j < n);
}

void init(){
  for(int i = 0; i <302; i++) fill(board[i], board[i]+302, 0);
  for(int i = 0; i <302; i++) fill(vis[i], vis[i]+302, false);
}

int bfs(int ci, int cj, int ti, int tj){

  queue<pair<pair<int,int>, int>> qu; //  {좌표, 이동 횟수}

  vis[ci][cj] = true;
  qu.push({{ci, cj}, 0});

  while(!qu.empty()){
    int curx = qu.front().X.X;
    int cury = qu.front().X.Y;
    int curcnt = qu.front().Y;
    qu.pop();

    if(curx == ti && cury == tj){ // 목적지 좌표 도착 
      return curcnt;
    }

    for(int i = 0; i < 8; i++){
      int nx = curx + dx[i];
      int ny = cury + dy[i];

      if(!checkrange(nx, ny) || vis[nx][ny]) continue;
      vis[nx][ny] = true;
      qu.push({{nx,ny}, curcnt + 1});
    }

  }
  return 0;
}

int main(void) {
  ios::sync_with_stdio(0);
  cin.tie(0);

  cin >> tc;

  while(tc--){
    init(); // 체스판과 방문배열 초기화
    cin >> n; // 체스판 한 변의 길이
    cin >> curx >>  cury >> targetx >> targety; // 현재칸, 목적지 칸
    int cnt = bfs(curx, cury, targetx, targety);
    cout << cnt << '\n';
  }

  return 0;
}

리뷰

기본적인 bfs 문제였다.
상하좌우 4칸이 아니라, 나이트가 갈 수 있는 (1, 2) 만큼 차이나는 8칸을 모두 확인해야 한다.

bfs 큐는 좌표와 이동횟수를 함께 넣어준다.
유효범위 인지 확인하고, 방문하지 않았는지 확인한 다음 큐에 넣어준다.

문제

빙산 2573번

"맞았습니다"코드

#include <bits/stdc++.h>
#define X first
#define Y second
using namespace std;

int n, m, year, areacnt;
bool goflag = true;
int area[303][303];
int vis[303][303];

int dx[] = {1, 0, -1, 0};
int dy[] = {0, 1, 0, -1};

bool check(int i, int j) {
  return (i >= 0 && i < n && j >= 0 && j < m);
}

void initvis(){ 
  for(int i = 0; i < n; i++) fill(vis[i], vis[i] + m, 0);
}

int melting(){ // 녹는 높이 계산해서 0이 된 칸의 개수를 센다

  int zero[303][303] = {0};
  int zerocnt = 0;

  for(int i = 0; i < n; i++){
    for(int j = 0; j < m; j++){
      if(area[i][j] == 0) continue;
      for(int z = 0; z < 4; z++){ // 주변의 0의 개수를 센다
        int nx = i + dx[z];
        int ny = j + dy[z];
        if(!check(nx, ny)) continue; // 유효 인덱스 체크
        if(area[nx][ny] == 0) zero[i][j]++;
      }
    }
  }

  for(int i = 0; i < n; i++){
    for(int j = 0; j < m; j++){
      area[i][j] = area[i][j]- zero[i][j];
      if(area[i][j] > 0) continue;
      area[i][j] = 0; zerocnt++; // 0이 된 칸의 개수
    }
  }

  return zerocnt;
}

void bfs(int x, int y){

  queue<pair<int,int> > qu; // {좌표 x, y}

  vis[x][y] = 1; // 현재 위치 방문
  qu.push({x, y});

  while(!qu.empty()){
    int curx = qu.front().X;
    int cury = qu.front().Y;
    qu.pop();

    for(int i = 0; i < 4; i++){
      int nx = curx + dx[i];
      int ny = cury + dy[i];
      if(!check(nx, ny) || vis[nx][ny] == 1 || area[nx][ny] <= 0) continue; // 정상 범위, 첫 방문, 이동가능 체크
      vis[nx][ny] = 1; // 방문표시
      qu.push({nx, ny}); // 이동
    }
  }
}

int main(void) {
  ios::sync_with_stdio(0);
  cin.tie(0);

  cin >> n >> m;
  for(int i = 0; i < n; i++){
    for(int j = 0; j < m; j++) {
      cin >> area[i][j];
    }
  }

  while(goflag){

    // 빙산 녹이기. 다 녹았으면 탈출.
    if(melting() == (m*n)){ year = 0; break; }

    year++; // 1년 추가
    initvis(); // 방문배열 초기화
    areacnt = 0; // 덩어리 개수 

    for(int i = 0; i < n; i++) { 
      for (int j = 0; j < m && goflag; j++) {
        if(area[i][j] <= 0 || vis[i][j]) continue; // 첫방문, 높이존재 여부
        bfs(i, j);
        areacnt++; 
        if(areacnt > 1){ goflag = false; break;} // 덩어리 2개 이상면 탈출
      }
    }
  }

  cout << year;
  return 0;
}

리뷰

코드의 흐름은 아래와 같다.

1. 빙산 녹이기
2. 1년이 흐른다
3. 방문 배열 초기화. 덩어리 표시 용도다.
4. 높이가 존재하는 빙산이 있다면 bfs를 시작한다. bfs로 한 덩이 범위를 vis 방문배열에 표시한다.
5. 덩어리가 2개 이상이 되면 탈출한다.

melting()

빙산이 녹을 때 특정 좌표 기준으로 동서남북을 확인한다. 여기서 즉시 빼버리면(== 빙산을 녹이면) 동서남북의 0 의 개수가 자꾸 달라진다.
동서남북을 확인해서 0의 개수를 셀 때, 이것을 저장할 따로 배열을 둬야 한다.

빙산이 녹을 때 음수가 되는 경우가 있는데, 0으로 바꿔줘야 한다.
음수가 됬을 때만 0이 됬다고 틀리게 코딩해서 초반에 오래 헤맸던 문제.

문제

불! 백준 4179 c++

"맞았습니다."코드 

#include <bits/stdc++.h>
#define X first
#define Y second
using namespace std;

// 4179 불!
int R, C;
char m[1002][1002];
bool vis[1002][1002];
int dx[] = {1, 0, -1, 0};
int dy[] = {0, 1, 0, -1};
bool exitflag = false;
queue<pair<int,int>> qf; // {좌표}
queue<pair<int,int>> qh; // {좌표}

bool checkrange(int i, int j){
  return (i >= 0 && i < R && j >= 0 && j < C);
}

int bfs(){

  int time = 0;

  while(!qh.empty() && !exitflag){
    time++;
    int hsize = qh.size();
    int fsize = qf.size();

    while(fsize--){
      int cx = qf.front().X;
      int cy = qf.front().Y;
      qf.pop();

      for(int i = 0; i < 4; i++){
        int nx = dx[i] + cx;
        int ny = dy[i] + cy;

        if(!checkrange(nx, ny) || m[nx][ny] == '#' || vis[nx][ny]) continue;
        m[nx][ny] = 'F';
        vis[nx][ny] = true;
        qf.push({nx,ny});
      }
    }

    while(hsize--) {
      int cx = qh.front().X;
      int cy = qh.front().Y;
      qh.pop();

      if (cx == 0 || cy == 0 || cx == (R-1) || cy == (C-1)) {
        exitflag = true;
        break;
      }

      for(int i = 0; i < 4; i++){
        int nx = dx[i] + cx;
        int ny = dy[i] + cy;

        if (!checkrange(nx, ny) || m[nx][ny] == '#' || vis[nx][ny]) continue;
        vis[nx][ny] = true;
        qh.push({nx,ny});
      }
    }
  }
  return time;
}

int main(void) {
  ios::sync_with_stdio(0);
  cin.tie(0);

  cin >> R >> C; // 행, 열
  for(int i = 0; i < R; i++){
    for(int j = 0; j < C; j++){
      cin >> m[i][j];
      if(m[i][j] == 'J') {
        qh.push({i, j}); m[i][j] = '.'; vis[i][j] = true;
      }
      else if (m[i][j] == 'F') {
        qf.push({i, j}); vis[i][j] = true;
      }
      else if (m[i][j] == '#') vis[i][j] = true;
    }
  }

  int answer = bfs();

  if(exitflag){
    cout << answer;
  }else{
    cout << "IMPOSSIBLE";
  }

  return 0;
}

리뷰 

불과 지훈이의 큐 

불의 시작점이 여러개가 주어지는 경우가 있다는걸 간과하고 처음에 헤맸다.

불의 시작점은 qf에 모두 넣었다. 

불이 번지면 맵에 F로 표시했다. 

지훈이의 시작점 J는 qh에 넣는다. 

J는 불이 여기로 이동할 수 있는 칸이니까 . 으로 바꿔서 입력받도록 했다. 

불과 지훈이의 이동 순서 

만약 점이 1개라면, 불의 이동과 지훈이의 이동이 동시라고 했을 때 지훈이는 탈출하지 못한다. 

따라서 불이 1칸 번지고, 지훈이가 1칸 이동하는 순서로 이동시켜야 한다. 불 1번, 지훈이 1번 이렇게 갈아서 이동시켜야 한다.  

지훈이가 탈출하는 것이 중요하니까 지훈이가 이동할 수 있는 곳은 모두 이동해봐야 한다. 

그래서 가장 바깥의 while문의 조건은 지훈이 큐 qh가 빌 때까지 돌린다. 

탈출 지점의 조건

맵의 가장자리에 가야 지훈이가 탈출한다.  

exitflag를 둬서 탈출하면 가장 바깥의 while 문을 탈출하도록 했다. 

pop 했을 때 좌표가 행이 0 또는 마지막행이면 된다. 열이 0이 되거나 마지막 열이면 탈출이다. 

문제

토마토 백준 7576

"맞았습니다" 코드

#include <bits/stdc++.h>
#define X first
#define Y second
using namespace std;

int m, n, totalcnt, sweetcnt;
int day = 1e9;
int box[1002][1002];
int dx[] = {1, 0, -1, 0};
int dy[] = {0, 1, 0, -1};
queue<pair<pair<int,int>, int>> qu; // {좌표, 일수}

bool checkrange(int i, int j){
  return (i >= 0 && i < n && j >= 0 && j < m);
}

void bfs(){
  while(!qu.empty()){
    int cx = qu.front().X.X;
    int cy = qu.front().X.Y;
    int cday = qu.front().Y;
    qu.pop();
    sweetcnt++;

    day = cday;
    //cout << "sweetcnt:" << sweetcnt << '\n';

    for(int i = 0; i < 4; i++){
      int nx = dx[i] + cx;
      int ny = dy[i] + cy;

      if(!checkrange(nx, ny) || box[nx][ny] != 0) continue;
      box[nx][ny] = 1; // 익히기
      qu.push({{nx, ny}, cday+1});
    }
  }
}

int main(void) {
  ios::sync_with_stdio(0);
  cin.tie(0);

  cin >> m >> n; // 가로, 세로

  for(int i = 0; i < n; i++){
    for(int j = 0; j < m; j++) {
      cin >> box[i][j];
      if (box[i][j] != -1) totalcnt++; // 토마토 총 개수 세기
      if (box[i][j] == 1) {
        qu.push({{i, j}, 0}); // 익은 토마토는 시작점
      }
    }
  }

  if(totalcnt == sweetcnt) cout << 0;
  else bfs();

  if(totalcnt == sweetcnt) cout  << day;
  else cout << -1;

  return 0;
}

리뷰

입력 받을 때 총 토마토의 개수를 세 둔다.
토마토가 모두 익지 않았을 때 -1을 출력해야 하기 때문이다.
익은 토마토의 주변에 있는 토마토를 익힐 수 있으니까 처음에 입력받을 때 '익은 토마토의 좌표'를 모두 큐에 넣는다.

bfs를 수행할 때, 큐에는 좌표와 날짜를 함께 저장한다. 

좌표의 유효범위를 확인하고, 안익은 토마토가 있으면 익은 것으로 바꾼다. 

목차

0x00 수식의 괄호 쌍이란?

0x01 문제 해결을 위한 관찰

0x02 문제 해결 방법

0x03 연습문제

0x00 수식의 괄호 쌍이란? 

수식의 괄호 쌍이 짝이 맞는지 확인해보자. 

( 이 있으면 ) 으로 닫아야 짝이 맞다. { 이 있으면 } 이 있어야한다. 

두 번째 식에서 (12+4} 여기가 틀렸다. 이와 같이 수식의 괄호 쌍이란, 주어진 괄호 문자열이 올바른지 판단하는 문제다. 

0x01 문제 해결을 위한 관찰 

아래의 3개 수식 중에 올바른 괄호 쌍은 무엇 무엇이 있을까? 

결론부터 말하면 첫 번째 식만 올바른 괄호 쌍이다. 

판단 방법 중에 가장 보편적인 방법은 바로 안쪽부터 짝 맞추기를 해서 지워나가는 방법이다. 

그리고 관찰력이 뛰어나다면,  ')' 의 개수가 '(' 의 갯수를 넘지 않으면 된다는 사실도 있다. 

괄호의 종류가 () 말고도 {}, [] 이 있다면, 여는 괄호의 갯수와 닫는 괄호의 갯수 비교만으로 해결되지 않는다. 

우리는 머릿속으로 어떤 로직을 거쳐서 판단한 걸까? 생각의 과정을 관찰하여 코드로 구현해보자. 

스택을 이용하여 구현해보자. 

아래의 관찰을 인지해야 한다. 

"닫는 괄호는 남아있는 괄호 중에서
가장 최근에 읽은 여는 괄호와 짝을 지어 없애버리는 명령이다. " 

1. 스택을 하나 두고, 문자열을 읽어 나가다가 여는 괄호를 만나면 모두 스택에 넣는다. 

2. 문자열을 읽어 나가다가 닫는 괄호를 만나면 스택의 top을 확인한다. 

3. 지금 읽은 것이 닫는 괄호이고 스택의 top이 여는괄호라면?  쌍이 올바른 것이다.

4. 따라서 스택의 top인 여는 괄호를 스택에서 지운다. pop() 

올바르지 않은 괄호 쌍 

올바르지 않은 괄호 쌍의 경우, 과정을 살펴보자. 

1. 문자열을 읽다가 만난 여는 괄호 2개는 모두 스택에 넣는다. 

2. 닫는 괄호 ) 를 만나면, 스택의 top을 확인한다. 

현재 스택의 top은 { 이다. 

3. 스택의 top인 {와 닫는괄호 ) 는 짝이 안맞는다. 

올바르지 않은 괄호 쌍의 예시 2가지 

1. 문자열을 끝까지 읽었는데, 스택에 여는 괄호가 남아있다. 

2. 문자열을 끝까지 읽고 스택도 비었는데, 닫는 괄호가 남아있다. 

0x02 문제 해결 방법 

올바른 괄호 쌍 판단을 위해 문제 해결 방법을 정리해본다. 

1. 여는 괄호가 나오면 스택에 추가.

2. 닫는 괄호가 나왔을 경우, 스택의 top이 짝이 맞는 괄호라면 pop 

3. 스택에 괄호가 남아있지 않으면 올바른 괄호 쌍. 

스택이 비었을 때 top을 참조하면 런타임에러!

0x03 연습문제 

수식의 괄호쌍이 코딩테스트에서 무조건 나온다고 할 정도로 중요하진 않지만,

stack을 이용한 문제가 많기 때문에 연습문제를 꼭 풀어보자. 

다음 시간에는 BFS를 배운다. 

공부 자료 출처 : 바킹독 알고리즘 수식의 괄호 쌍

문제

그림 백준 1926

"맞았습니다" 코드

#include <bits/stdc++.h>
#define X first
#define Y second
using namespace std;
​
int n, m; // 세로, 가로
int board[502][502];
int v[502][502]; // 방문했으면 1로 표시
int dx[] = {0, 1, 0, -1};
int dy[] = {1, 0, -1, 0};
​
int cnt, answer; // 그림 개수와 넓이.
​
int bfs(int a, int b){
​
    queue<pair<int,int> > q;
    int num = 0;
​
    // 방문표시 후, 큐에 넣기.
    v[a][b] = 1;
    q.push({a,b});
​
    while(!q.empty()){
​
        int x = q.front().X;
        int y = q.front().Y;
        q.pop();
        num++;
        for(int i = 0; i < 4; i++){
            int tempX = x + dx[i];
            int tempY = y + dy[i];
​
            if(tempX < 0 || tempX >= n || tempY < 0 || tempY >= m) continue; // 범위 초과는 탈출
            if(v[tempX][tempY] == 1) continue; // 이미 방문한거면 지나감
​
            if(board[tempX][tempY] == 1){ // 그림영역이라면 방문표시 후 큐에 넣기.
                board[tempX][tempY] = 2;
                v[tempX][tempY] = 1;
                q.push({tempX, tempY});
            }
        }
    }
​
    return num;
}
​
int main(void) {
    ios_base::sync_with_stdio(0);
    cin.ignore(0);
​
    cin >> n >> m;
​
    for(int a = 0; a < n; a++){
        for(int b = 0; b < m; b++){
            cin >> board[a][b];
        }
    }
​
    for(int a = 0; a < n; a++){
        for(int b = 0; b < m; b++){
​
            if(board[a][b] == 0 || v[a][b] == 1) continue;
            cnt++; //그림 개수 카운트
            answer = max(answer, bfs(a,b)); // 최대 넓이 찾기 
​
        }
    }
​
    cout << cnt << '\n' << answer;
    return 0;
}

리뷰

BFS 기본 형태의 문제다.

인덱스 확인 후 그림영역에 방문 표시를 한다음에 방문한 좌표를 push()를 해줘야하는데.

그거 하나 틀려서 시간을 많이 잡아먹었다.