백준 - 23747 와드

문제

https://www.acmicpc.net/problem/23747

23747번: 와드

여행 기록을 입력받아 맵에서 이동하고, 기록이 W일 경우에 같은 구역의 시야를 밝힌 후 모든 여행이 끝난 후의 맵의 시야를 출력하는 문제였다.

 

문제 풀이

입력받은 방향대로 이동하다가  W가 나오면 dfs를 호출해 같은 구역(같은 문자)인 곳을 탐색해줬다.

마지막에 이동한 곳과 그 위치의 상하좌우까지 방문처리 해준 후, isVisit 값이 true면 .을 false면 #을 출력했다.

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int R,C;
char map[1001][1001];
bool isVisit[1001][1001];

//상하좌우
int dx[4] = {-1,1,0,0};
int dy[4] = {0,0,-1,1};

int findDir(char a){
    if(a=='U') return 0;
    else if(a=='D') return 1;
    else if(a=='L') return 2;
    else if(a=='R') return 3;
    else return -1;
}

bool isInside(int x, int y){
    if(x>0 && y>0 && x<=R && y <=C) return true;
    return false;
}

void dfs(int x, int y, char nowChar){
    isVisit[x][y] = true;
    
    for(int i=0;i<4;i++){
        int nx = x + dx[i];
        int ny = y + dy[i];
        
        if(isInside(nx,ny) && map[nx][ny] == nowChar && isVisit[nx][ny] == 0){           
            dfs(nx,ny,nowChar);
        }
    }
}

int main(int argc, char** argv)
{
    scanf("%d %d",&R,&C);
    
    string str;
    for(int i=1;i<=R;i++){
        cin>>str;
        for(int j=1;j<=C;j++){
            map[i][j] = str[j-1];            
        }
    }
    
    int x,y;
    scanf("%d %d",&x,&y);
    
    cin>>str;
    for(int i=0;i<str.length();i++){
        int nowDir = findDir(str[i]);
        if(nowDir == -1){ //W
            //printf("와드! map[%d][%d]: %c\n",x,y,map[x][y]);
            dfs(x,y,map[x][y]);
        }
        else{ //이동
            
            x += dx[nowDir];
            y += dy[nowDir];
            //printf("이동! dir: %c map[%d][%d]: %c\n",nowDir, x,y,map[x][y]);
        }        
    }
    
    //printf("마지막 위치 : map[%d][%d]: %c\n",x,y,map[x][y]);
    isVisit[x][y] = true;
    for(int i=0;i<4;i++){
        int nx = x+dx[i];
        int ny = y+dy[i];
        
        if(isInside(nx,ny)){
            isVisit[nx][ny] = true;
        }
    }
    
    int answer = 0;
    
    for(int i=1;i<=R;i++){
        for(int j=1;j<=C;j++){
            if(isVisit[i][j]) printf(".");
            else printf("#");
        }
        printf("\n");
    }
    
    
    
    return 0;
}