JArchive 프로그래밍 일기

문제

숨바꼭질3 백준 13549

"맞았습니다" 코드

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

int n, k;
int vis[100005];

bool rangecheck(int x){
  return (x >=0 && x <= 100000);
}

void bfs(){

  queue<int> qu;

  vis[n] = 0; // 수빈이의 현재 위치는 0초에 도달.
  qu.push(n);

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

    if(cx == k){
      cout << vis[cx]<< '\n';
      break;
    }

    for(auto nx : {cx*2, cx + 1, cx - 1}){

      if(!rangecheck(nx) || vis[nx] <= (vis[cx]+1)) continue;

      if((cx*2) == nx) {
        vis[nx] = vis[cx];
      }else{
        vis[nx] = vis[cx] + 1;
      }
      qu.push(nx);
    }
  }
}

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

  int bignum = 1e9;
  fill(vis, vis+100004, bignum);

  cin >> n >> k;

  bfs();

  return 0;
}

리뷰

다시 풀어봐야 할 문제.

내가 위치 2에 있다.
위치 2에서 '위치 4'로 이동할 때, 예전에 방문할 때 보다 '적은 시간'이 걸려야 한다.
즉, '위치 4'로 가는 시간이 2초가 걸릴 수도 있고, 0초가 걸릴 수도 있다.

현재 위치2 이고, 이동 방법은 x2 해서 순간이동 하는방법, +1또는 -1하는데 1초가 걸리는 방법이 있다.
+1 을 2번 하면 2초가 걸려서 위치 4에 도착할 수 있다.
x2를 하고 순간이동하면 0초가 걸려서 위치 4에 도착할 수 있다.

따라서 위치 배열 인덱스 4에는 '0초'가 저장되어야 한다.

'가장 빠른 시간' 을 구해야 하니까 모든 위치의 초기 시간값을 2^9 로 크게 잡아놨다.

bfs로 순회할 때, "예전에 방문할 때 보다 '적은 시간'이 걸려야 한다" 를 만족시키기 위한 조건이 필요했다.

그래서 '현재시간 +1초' 와 다음위치가 저장하고 있는 도달 시간을 비교했다. 다음위치가 저장하고 있는 도달 시간이 더 커야 이동할 수 있게 했다.

현재 위치 시간이 2초 라고 했을 때. 2초 + 1초, 즉 3초가 다음 위치에 저장할 시간이 된다.
현재까지는 2초가 걸렸고 다음 위치에는 3초가 걸릴 수 있는 방법으로 현재까지 도달해왔다는 뜻이다.

다음 위치에 이미 3초가 저장되어 있다면, 다음 위치의 시간을 더 짧게 갱신해줄 필요가 없다.
다음 위치에 만약 4초가 저장되어 있다면, 3초를 저장하려고 했으니까 갱신해주면 된다.

문제

적록색약 백준 10026

"맞았습니다" 코드

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

int n, nor, abnor;
int arr[102][102];
bool vis[102][102] = {false};
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 < n);
}

void bfs(int i, int j, int target){
  queue<pair<int,int>> qu;

  vis[i][j] = true;
  qu.push({i, j});

  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) || (arr[nx][ny]!=target) || vis[nx][ny]) continue;
      vis[nx][ny] = true;
      qu.push({nx,ny});
    }
  }
}

void input(){
  cin >> n;

  string str = "";

  for(int i = 0; i < n; i++){
    cin >> str;
    for(int j = 0; j < n; j++){
      switch(str[j]){
        case 'R':
          arr[i][j] = 1; break;
        case 'G':
          arr[i][j] = 2; break;
        case 'B':
          arr[i][j] = 3; break;
      }
    }
  }
}
int main(void) {
  ios::sync_with_stdio(0);
  cin.tie(0);

  input();

  for(int i = 0; i < n; i++){
    for(int j = 0; j < n; j++){
      if(!vis[i][j]) {
        bfs(i, j, arr[i][j]);
        nor++;
      }
    }
  }

  // R -> G 으로 변경.
  for(int i = 0; i < n; i++){
    for(int j = 0; j < n; j++){
      if(arr[i][j] == 1) arr[i][j] = 2;
    }
  }

  // 방문배열 초기화
  for(int i = 0; i < n; i++) fill(vis[i], vis[i]+n,0);

  for(int i = 0; i < n; i++){
    for(int j = 0; j < n; j++){
      if(!vis[i][j]) {
        bfs(i, j, arr[i][j]);
        abnor++;
      }
    }
  }

  cout << nor << ' '<< abnor;
  return 0;
}

리뷰

유기농 배추 문제와 비슷한 기본적인 bfs 문제였다.

R, G, B 문자는 숫자로 변경해서 저장했다. 나는 string을 이용해서 한 줄 받은다음에, 하나씩 int로 넣었는데.
다른분 코드를 보니 int 그대로 저장하는 방법도 있었다.

코드 순서는 아래와 같다.

1. 이중 for문을 돌면서, 방문하지 않은 칸인 경우 bfs를 시작한다. 이 때, 파라미터로 현재 칸의 색깔숫자를 넘긴다.
2. 현재 칸의 색깔 숫자와 같으면서도 미방문인 칸을 큐에 push하면서 bfs를 수행한다.
3. 이렇게 bfs를 돌리면서 vis배열이 꽉 차면 적록색약이 아닌사람이 볼 떄의 공간개수가 nor에 저장된다.
4. 적록색약인 경우 1인 칸과 2인칸이 똑같이 보이도록 1을 2로 바꿔준다. 이중 for문을 돈다.
5. 방문 배열을 초기화한다.
6. 현재 칸의 색깔 숫자와 같으면서도 미방문인 칸을 큐에 push하면서 bfs를 수행한다. 이 때 bfs를 도는 횟수가 abnor에 저장된다. ( abnor == 적록색약인 사람이 구분하는 영역의 개수)

문제

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

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