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를 수행할 때, 큐에는 좌표와 날짜를 함께 저장한다. 

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

문제

그림 백준 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()를 해줘야하는데.

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

문제

괄호의 값 2504

"맞았습니다" 코드

#include <bits/stdc++.h>
using namespace std;
​
stack<char> s;
string str;
​
int main(void) {
    ios_base::sync_with_stdio(0);
    cin.ignore(0);
​
    getline(cin, str);
​
    bool check = true; // 짝이 안맞는 틀린 괄호인지 체크 
​
    int sum = 0; // 누적해서 더해질 값
    int num = 1; // 곱해질 값
​
    for(int i = 0; i < str.length(); i++){ // 괄호가 틀린 경우를 필터링
​
        if(str[i] == '(' || str[i] == '[') {
            s.push(str[i]); continue;
        }
        else if(str[i] == ']' && s.size() > 0){
            if(s.top() == '[') {
                s.pop();
                continue;
            }
        }
        else if(str[i] == ')' && s.size() > 0){
            if(s.top() == '(') {
                s.pop();
                continue;
            }
        }
        check = false; break;
    }
​
    if(!check || !s.empty()){ // 틀린 괄호쌍이니까 0 출력 후 종료 
        cout << '0';
        return 0;
    }
​
    while(1){ // 스택이 비어 있도록 처리
        if(s.empty()) break;
        s.pop();
    }
​
    for(int i = 0; i < str.length(); i++){
​
        if(str[i] == '('){
            s.push(str[i]);
            num *= 2; // 여는 괄호들이 겹치면 2배가 된다.
        }
        else if(str[i] == ')'){
​
            if(str[i-1] == '('){ // 직전 괄호가 여는 괄호였다면
                sum += num;
            }
            s.pop();
            num /= 2;  // 괄호 () 한쌍이 제거됬으니까 곱해질 값을 /2 해준다.
        }
        else if(str[i] == '['){
            s.push(str[i]);
            num *= 3;
        }
        else if(str[i] == ']'){
​
            if(str[i-1] == '['){ // 직전 괄호가 여는 괄호였다면
                sum += num;
            }
            s.pop();
            num /= 3;  // 괄호 [] 한쌍이 제거됬으니까 곱해질 값을 /3 해준다.
        }
    }
​
    cout << sum;
​
    return 0;
}

리뷰

맞왜틀 하면서 골머리싸맸다.

초반에는 스택이 비어있을 수 있는데 top을 참조하니까 런타임 에러가 났다.

스택 size()를 확인하면서 처리하자니 조건문이 깊어졌다.

그래서 앞단에서 '틀린 괄호쌍'을 걸러내도록 하는 for문을 두도록 구조를 바꿨다.

일단 틀린 괄호쌍을 걸러내고, 두 번째 for문 에서는 계산만 하도록 했다.