[SWEA] 1979 어디에 단어가 들어갈 수 있을까

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5PuPq6AaQDFAUq

SW Expert Academy

#include<cstdio>
#include<cstring>
typedef long long ll;
using namespace std;
int main()
{

	int board[15][15];
	int flag,flag2;
	int result;
	int size;
	int N,K; // N = Board, K는 단어 길이 
	scanf("%d",&size);
	for(int i = 0; i < size; i++){
		scanf("%d %d",&N,&K);
		for(int x = 0; x < N; x++)
		{
			for(int y = 0; y < N; y++)
			{
				scanf("%d",&board[x][y]);
			
			}
		}
		result = 0;
		
		for(int x = 0; x < N; x++)
		{
			for(int y = 0; y < N; y++)
			{
				flag = 0;
				flag2 = 0;
				if(board[x][y] == 0) continue;
		
				//가로	
				for(int a = 1; a < N; a++)
				{
					if( y>0 && board[x][y-1] == 1) break;
					// x > 0 조건 때문에 1 1 1 0 0 일때 길이 2를 못잡아냄. 
					if( y+a >=0 && y+a < N && board[x][y+a] == 1)
					{
						flag++;
					}
					else break;
				}
				if(flag == K-1) 
				{
					//printf("flag 1 = x= %d y = %d\n",x,y);
					result++;
				}
				
				
				//세로 
				for(int a = 1; a < N; a++)
				{	
					if( x>0 && board[x-1][y] == 1) break;
					
					if( x+a >=0 && x+a < N && board[x+a][y] == 1){
						flag2++;
					} 
					else break;
				}
				
				
				if(flag2 == K-1)
				{
					//printf("flag 2 = x= %d y = %d\n",x,y);
					result++;
				}
				 
			}
		}
		printf("#%d %d\n",i+1,result);
	}

	 
	
	return 0;
 } 

 

내 풀이법:

점 하나마다 오른쪽, 아래쪽 탐색 하려고 했다.

1. 문제점 :

대표사진 삭제

사진 설명을 입력하세요.

이렇게 가운데에 3칸씩 가는건 인정이 안된다.

딱 3칸으로 들어 맞아야 카운트가 올라간다.

 

2. 맨 위에 붙어있거나, 맨 왼쪽에 붙어있으면 출발점이 될 수 있다.

또한 바로 왼쪽에 검은 벽이 있어서 바로 다음 흰색 타일은 (ex 3번) 또 출발점이 될 수 있다.

 

해결 방법 :

1. 가로 방향으로 쭉 가면서 flag로 길이를 잰다. 만약 길이 막혔거나, 검은 벽을 만나면 탈출한다.

나간 후에 flag와 distance를 비교하여 같으면 단어가 들어갈 수 있는것이고, 같지 않으면 막혀있거나 범위를 벗어난것이다.

2. 세로도 마찬가지로 수행한다.

3. x = 0 과 y = 0 인 라인은 모두다 시작점이 될 수 있다. 따라서 별 제약 없이 넘어간다.

 

하지만 x > 1 , y > 1 인 부분들은 시작점이 될 수도 있고, 안될수도 있다.

 

그러면 어떻게 확인하는가?

바로 왼쪽 이나 바로 위에가 벽돌로 막혀있는지만 체크하면 된다.

 

if( y>0 && board[x][y-1] == 1) break;

이 뜻이 첫번째 칸이 넘으면서 옆이 흰 벽돌이면 그냥 나가고 아니면 계속 하라는 의미이다.

 

---

시간이 오래걸린 이유:

 

처음에 별로 생각하기 싫어서 가로 세로 모두 다

x > 0 && y > 0 을 넣었는데 이것 때문에 몇시간이 걸렸다.

 

아래와 같은 식에서 distance 2는 나올수가 없는데 내가 x와 y가 모두 0 이상일때라고 해서 기준점을 판단하는 조건문을 넘어가서

x = 0, y= 1 에서 distance 2로 인지해버렸다..

1 1 1 0 0

0 0 0 0 0

0 0 0 0 0

0 0 0 0 0

0 0 0 0 0

 

만약 가로를 체크할 경우 y가 0보다 크면 x와 관계없이 무조건 기준점이 될 수 있기때문에 X>0 을 지웠어야 했다.

 

 

끝.