[C] 21736: 헌내기는 친구가 필요해

간단하게 풀 수 있는 문제였다.

X가 벽이고 O로 지나갈 수 있으며 P를 만날때 people++을 해주면 된다.

그리고 결국 그래프를 순회만 하면 되기 때문에 Depth-first를 이용해 풀어주었다

 

#include <stdio.h>
#include <string.h>

char graph[601][601];
int visit[601][601];
int people=0;
int x_coordinate[4]={0,0,1,-1};
int y_coordinate[4]={1,-1,0,0};

void dfs(int x,int y,int x_max,int y_max)
{
  for(int i=0;i<4;i++)
    {
      int nx=x+x_coordinate[i];
      int ny=y+y_coordinate[i];
      if(nx<0||ny<0||nx>x_max-1||ny>y_max-1) //범위에서 벗어남
        continue;
      if(graph[ny][nx]=='X'|| visit[ny][nx]==1) //벽이 있거나 이미 지나간 공간
        continue;
      
      if(graph[ny][nx]=='P') //사람을 만났을 때 people++
        people++;
      visit[ny][nx]=1;
      dfs(nx,ny,x_max,y_max);
      
    }
}

int main(void)
  {
    int y,x,y_cd,x_cd;
    scanf("%d %d",&y,&x);
    for(int j=0;j<y;j++)
      {
        scanf("%s",graph[j]);
        for(int i=0;i<x;i++)
          {
            if(graph[j][i]=='I')
            {
              x_cd=i,y_cd=j;
            }
          }
      }
    visit[y_cd][x_cd]=1;
    dfs(x_cd,y_cd,x,y);
    //printf("people: %d\n",people);
    if(people!=0)
      printf("%d",people);
    else
      printf("TT");
  }