코드업 2610 : 그림판 채우기

문제

2610 : 그림판 채우기

10∗10 크기의 그림이 있다.
이 그림에 그림판 색 채우기 기능을 구현하시오.
(단, 원점은 왼쪽 위 끝이고, x값은 오른쪽, y값은 아래로 갈수록 증가한다.)

 

 

입력

10∗10 크기의 그림과 색칠할 좌표의 x, y 값이 차례로 입력된다.
_ 는 색칠되지 않은 부분이고 * 는 색칠된 부분이다.

출력

색 채우기를 한 결과를 출력한다.

 

입력 예시

__________
_____****_
_____*__*_
__*******_
__*__*_**_
__*__****_
__*____*__
__*____*__
__******__
__________
6 2

 

출력 예시

__________
_____****_
_____****_
__*******_
__*__*_**_
__*__****_
__*____*__
__*____*__
__******__
__________

 

---

MY CODE

#include <stdio.h>
char a[20][20];

void fill(int x, int y){
	if (x==-1||x==10||y==-1||y==10) return; 
	if (a[x][y]=='*') return; 
    else (a[x][y]='*');
    fill(x-1, y); 
    fill(x, y+1); 
	fill(x+1, y); 
    fill(x, y-1); 
}

int main()
{
    for(int i=0; i<10; i++){
    	for(int j=0; j<10; j++){
    		scanf("%c", &a[i][j]);
		}
        getchar(); 
    }
    int x, y;
    scanf("%d%d", &x, &y);
    fill(y, x); 
    for(int i=0; i<10; i++){
        for(int j=0; j<10; j++){
            printf("%c", a[i][j]);
        }
        puts(""); 
    }
    return 0;
}

 

코드설명

if (x==-1||x==10||y==-1||y==10) return;    

5줄 : 10*10범위를 넘어가면 return

 

if (a[x][y]=='*') return;     

6줄 : *, 즉 선에 위치하면 return

 

else (a[x][y]='*');     

7줄 : //_이면 *로 채우기

 

fill(x-1, y);     
fill(x, y+1);     
fill(x+1, y);     
fill(x, y-1);     

8줄 : //위로 탐색

9줄 : //왼쪽으로 탐색

10줄 : //아래로 탐색

11줄 : //오른쪽으로 탐색

 

getchar();     

20줄 : //엔터키를 받지 않기 위해 getchar 사용. j 범위를 11까지 두어도 같은 결과가 나온다.

 

fill(y, x);    

24줄 : //수학에서의 좌표평면을 따르기 때문에 입력받은 x, y를 바꿔 넣어야 함

 

puts("");     

29줄 : //줄바꿈

 

---

생겼던 문제점

자잘한 문제부터 큰 문제까지 꽤 이것저것이 있었는데요. 조금 알아보자면

 

1. 아무것도 손대지 않고 받은 배열을 출력했는데 다 출력이 되지 않음

 

배열을 공부하면서 생긴 습관 중 하나가, 일단 배열이 잘 받아졌는지 확인해 보는 것이 있었습니다.

 

이것도 평소처럼 확인을 하고자 printf문을 넣었는데 배열의 뒤에가 출력이 안 되더라고요. 

별 문제 없겠지, 그냥 진행할까 하다가도 뭔가 찝찝해 char 배열을 구글에 검색해 보았습니다. 

 

알고보니 원인은 scanf로 받다 보니 enter까지 같이 받아진 것에 있었습니다. 출력할 때 줄바꿈 안 해도 저절로 되는 거 보고 눈치챘어야 하는데... 신경 쓸 일은 많이 없지만 정말 중요한 부분을 다시 상기하게 되었습니다. 

 

저는 해결하기 위해 getchar를 넣었는데, 사실 getchar를 넣는 것 보다 배열을 j<10이 아니라 j<11로 받거나, 그냥 

for(int i=0; i<10; i++){
    scanf("%s", a[i]);
}

이런 식으로 코드를 고쳐 해결하는 것이 더 깔끔하고 좋습니다. 

 

 

2. 24줄에서 fill에 넣을 때 x, y를 바꿔 넣지 않음

바보같은... 실수.......

 

 

3. DFS구현 에러

void fill(int x, int y){
    if (a[x][y]!='*'){
        a[x][y]='*';
        if (a[x-1][y]!='*'){
        	fill(x-1, y);
		}
        else if (a[x][y-1]!='*'){
        	fill(x, y-1);
		} 
        else if (a[x+1][y]!='*'){
        	fill(x+1, y);
		} 
        else if (a[x][y+1]!='*'){
        	fill(x, y+1);
		}
    }
    else return; 
}

처음 제가 구현한 DFS함수입니다. 

 

일단 선 밖으로 나가는 경우의 코드를 추가하지 않았습니다.

 

또한 if 안에 재귀를 넣어서 아래와 같은 문제도 발생하였습니다. 

순서가 상->좌->하->우 이다 보니 우측으로 간다면 벽을 만날 때까지 쭉 가야 하는데 그냥 위로 올라가버려서 빈칸이 다 채워지지 않더라고요. 또한 공간을 한붓그리기로 이을 수 없는 모양이라면 전체를 채우기가 불가능했습니다. 여기서 많이 골머리를 썩혔습니다. 이것만 고치면 다 되는데 어떻게 해야 할 지를 모르겠더라고요.

 

 

결국 https://swblossom.tistory.com/83 를 참고했습니다. 

[C/C++] 코드업(codeup) 2610번 그림판 채우기

 

 

이분의 코드를 보면 저와 거의 유사한데, 다른 점이 재귀문을 if안에 넣지 않았다는 것입니다. 

void paint(int row, int col){
	//범위밖이면 리턴
	if(row==-1||col==-1||row==10||col==10) return;
	
	//색칠된 테두리라면 리턴 
	if(arr[row][col]=='*') return;
	
	//색칠안된 부분이라면 색칠
	if(arr[row][col]=='_') arr[row][col] = '*';
	
	//상, 하, 좌, 우 로 탐색
	paint(row-1, col);
	paint(row+1, col);
	paint(row, col-1);
	paint(row, col+1);
}

 

 

저는 재귀문을 if안에 넣어 한번 간 요소는 더이상 확인되지 않았는데, if밖에 상하좌우 모든 재귀문을 놓은 것을 보고 그제서야 DFS를 이해하게 되었습니다. 저렇게 되어야지 한 방향으로 가다가 막혔을 때 다시 돌아와서 다른 방향으로 갈 수 있으니까요. 

 

 

if문을 없애고 재귀를 밖에 꺼내 놓으니 코드가 문제 없이 잘 돌아갔습니다. 

void fill(int x, int y){
	if (x==-1||x==10||y==-1||y==10) return; 
	if (a[x][y]=='*') return; 
    else (a[x][y]='*');
    fill(x-1, y); 
    fill(x, y+1); 
	fill(x+1, y); 
    fill(x, y-1); 
}

 

 

---

순서도

---

다른 사람의 코드를 절대 참고 안 하는 편인데 이번 코드는 참고하게 되서 조금 아쉬웠습니다. 그러나 저 부분은 제가 혼자 아무리 고민했어도 DFS의 이해도가 낮아 혼자 힘으로는 해결되기는 어렵지 않았을까 싶습니다. 최선은 아니지만 차선이지 않았을까 싶어요. 대신 다른 DFS는 꼭 혼자 힘으로 풀어보려 합니다. 파이팅.

 

 

문제는 아래에 있습니다.

https://codeup.kr/problem.php?id=2610&rid=23688

그림판 채우기