글 읽기 - 손으로 그렸을때는 맞는것 같은데...TC에서는 틀리게 나옵니다

cheonilchu 5년 전 0

if문을 많이 사용하여 조금 난잡한 코드입니다.

11 10
7 4 0
1 1 1 1 1 1 1 1 1 1
1 0 0 0 0 0 0 0 0 1
1 0 0 0 1 1 1 1 0 1
1 0 0 1 1 0 0 0 0 1
1 0 1 1 0 0 0 0 0 1
1 0 0 0 0 0 0 0 0 1
1 0 0 0 0 0 0 1 0 1
1 0 0 0 0 0 1 1 0 1
1 0 0 0 0 0 1 1 0 1
1 0 0 0 0 0 0 0 0 1
1 1 1 1 1 1 1 1 1 1

이 테스트 케이스를 넣었을 때

11 10
7 4 0
1 1 1 1 1 1 1 1 1 1
1 0 0 0 0 0 0 0 0 1
1 0 0 0 1 1 1 1 0 1
1 0 0 1 1 2 2 2 2 1
1 0 1 1 2 2 2 * 2 1
1 0 0 0 2 2 2 2 2 1
1 0 0 0 2 2 2 1 2 1
1 0 0 0 2 2 1 1 2 1
1 0 0 0 2 2 1 1 2 1
1 0 0 0 2 2 2 2 - 1
1 1 1 1 1 1 1 1 1 1

*가 시작점이고 -가 최종점입니다.

조건을 맞춘것 같은데 TC와는 다른 29라는 count가 나옵니다...

어디서 잘못된것인지 모르겠습니다!

그리고 여기서 (r,c)는 (x,y)를 의미하는것인지 궁금합니다.

#include <stdio.h>
#include <stdlib.h>

int r, c, pdirection;
int map[51][51];
int rear = 0, front = 0;
int x[3000], y[3000];
int d;
int count;
int N, M;
int i, j;

enqueue(int _a, int _b, int _c)
{
	x[rear] = _a;
	y[rear] = _b;
	d = _c;
	rear++;
}

dequeue()
{
	front++;
}


solve(int _x, int _y, int _d)
{
	if (map[_y][_x] == 0) //처음 시작점이 청소할 공간이면 청소
	{
		map[_y][_x] = 2;
		count++;
	}
	
	enqueue(_x, _y, _d); // 시작점 push
	printf("%d x: %d y: %d d: %d count : %d\n", map[y[front]][x[front]], x[front], y[front], d, count);
	while (1)
	{
		if (d == 0) //청소기의 방향이 북쪽일때
		{
			if (map[y[front]][x[front] - 1] != 0 && map[y[front]][x[front] + 1] != 0 && map[y[front] - 1][x[front]] != 0 && map[y[front] + 1][x[front]] == 1 && d == 0)
			{// 서쪽 배열 !=0, 동쪽 배열 !=0, 북쪽배열 !=0, 남쪽 배열 ==1
				break; //탈출
			}
			if (map[y[front]][x[front]-1] == 0 && d == 0)//왼쪽의 배열이 비어 있고 d[front]가 0일때
			{
				enqueue(x[front] - 1, y[front], 3); //x의 좌표에 x-1 y의 좌표에 y 방향은 서쪽으로 변경
			}
			
			else if (map[y[front]][x[front] - 1] != 0 && map[y[front]][x[front] + 1] != 0 && map[y[front] - 1][x[front]] != 0 && map[y[front] + 1][x[front]] == 2 && d == 0)
			{// 서쪽 배열 !=0, 동쪽 배열 !=0, 북쪽배열 !=0, 남쪽 배열 ==2
				enqueue(x[front], y[front] + 1, 0); //방향은 북쪽 그대로, 남쪽으로 한칸 이동
			}
			else if((map[y[front]][x[front] - 1] == 1 || map[y[front]][x[front] - 1] == 2) && d == 0) // 왼쪽의 배열이 벽이거나 치운 자리일 경우 && d[front]가 0일때
			{
				enqueue(x[front], y[front], 3); //방향만 서쪽으로 전환
			}
			
			
		}
		else if (d == 1) //청소기의 방향이 동쪽일때
		{
			if (map[y[front]][x[front] - 1] == 1 && map[y[front]][x[front] + 1] != 0 && map[y[front] - 1][x[front]] != 0 && map[y[front] + 1][x[front]] != 0 && d == 1)

			{// 서쪽 배열 ==1, 동쪽 배열 !=0, 북쪽배열 !=0, 남쪽 배열 !=0
				break; //탈출
			}
			if (map[y[front]-1][x[front]] == 0 && d== 1)//북쪽의 배열이 비어 있고 d[front]가 1일때
			{
				enqueue(x[front], y[front]-1, 0); //x의 좌표에 x y의 좌표에 y+1 방향은 북쪽으로 변경
			}
			
			else if (map[y[front]][x[front] - 1] == 2 && map[y[front]][x[front] + 1] != 0 && map[y[front] - 1][x[front]] != 0 && map[y[front] + 1][x[front]] != 0 && d == 1)
			{// 서쪽 배열 ==2, 동쪽 배열 !=0, 북쪽배열 !=0, 남쪽 배열 !=0
				enqueue(x[front] - 1, y[front], 1); //방향은 동쪽 그대로, 서쪽으로 한칸 이동
			}
			else if((map[y[front]-1][x[front]] == 1 || map[y[front]-1][x[front]] == 2) && d == 1) // 왼쪽의 배열이 벽이거나 치운 자리일 경우 && d[front]가 1일때
			{
				enqueue(x[front], y[front], 0); //방향만 북쪽으로 전환
			}
			
		
		}
		else if (d == 2) //청소기의 방향이 남쪽일때
		{
			if (map[y[front]][x[front] - 1] != 0 && map[y[front]][x[front] + 1] != 0 && map[y[front] - 1][x[front]] == 1 && map[y[front] + 1][x[front]] != 0 && d == 2)

			{// 서쪽 배열 !=0, 동쪽 배열 !=0, 북쪽배열 ==1, 남쪽 배열 !=0
				break; //탈출
			}
			if (map[y[front]][x[front]+1] == 0 && d == 2)//동쪽의 배열이 비어 있고 d[front]가 0일때
			{
				enqueue(x[front]+1, y[front], 1); //x의 좌표에 x+1 y의 좌표에 y 방향은 동쪽으로 변경
			}
			
			else if (map[y[front]][x[front] - 1] != 0 && map[y[front]][x[front] + 1] != 0 && map[y[front] - 1][x[front]] == 1 && map[y[front] + 1][x[front]] != 0 && d == 2)
				// 서쪽 배열 !=0, 동쪽 배열 !=0, 북쪽배열 ==2, 남쪽 배열 !=0
			{
				enqueue(x[front], y[front]-1, 1); //방향은 동쪽 그대로, 서쪽으로 한칸 이동
			}
			else if ((map[y[front]][x[front+1]] == 1 || map[y[front]][x[front]+1] == 2) && d == 2) // 왼쪽의 배열이 벽이거나 치운 자리일 경우 && d[front]가 2일때
			{
				enqueue(x[front], y[front], 1); //방향만 동쪽으로 전환
			}
			
		
		}
		else if (d == 3) //청소기의 방향이 서쪽일때
		{
			if (map[y[front]][x[front] - 1] != 0 && map[y[front]][x[front] + 1] == 1 && map[y[front] - 1][x[front]] != 0 && map[y[front] + 1][x[front]] != 0 && d == 3)
			{// 서쪽 배열 !=0, 동쪽 배열 ==1, 북쪽배열 !=0, 남쪽 배열 !=0
				break; //탈출
			}
			if (map[y[front]+1][x[front]] == 0 && d == 3)//동쪽의 배열이 비어 있고 d[front]가 3일때
			{
				enqueue(x[front], y[front]+1, 2); //x의 좌표에 x y의 좌표에 y+1 방향은 남쪽으로 변경
			}
			
			else if (map[y[front]][x[front] - 1] != 0 && map[y[front]][x[front] + 1] == 2 && map[y[front] - 1][x[front]] != 0 && map[y[front] + 1][x[front]] != 0 && d == 3)
			{// 서쪽 배열 !=0, 동쪽 배열 ==2, 북쪽배열 !=0, 남쪽 배열 !=0
				enqueue(x[front] +1, y[front], 1); //방향은 동쪽 그대로, 서쪽으로 한칸 이동
			}
			else if ((map[y[front]+1][x[front]] == 1 || map[y[front]+1][x[front]] == 2) && d == 3) // 왼쪽의 배열이 벽이거나 치운 자리일 경우 && d[front]가 3일때
			{
				enqueue(x[front], y[front], 2); //방향만 남쪽으로 전환
			}
			
		
		}
		front++;
		
		
		if (map[y[front]][x[front]] == 0)
		{
			count++;
			map[y[front]][x[front]] = 2; //바뀐 자리가 0일 경우 청소 후, count +1
		}
		printf("%d x: %d y: %d d: %d count : %d\n", map[y[front]][x[front]], x[front], y[front], d, count);
	}
}

int main()
{
	int N, M;
	scanf("%d %d", &N, &M);
	scanf("%d %d %d", &r, &c, &pdirection);
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < M; j++)
		{
			scanf("%d", &map[i][j]);
		}
	}
	solve(r, c, pdirection); //0,0에서 배열은 시작하므로
	printf("%d\n", count);
}

djm03178 5년 전 0

힌트를 드리자면, 예제 2번의 경우 청소하는 순서는 다음과 같습니다. 1부터 차례대로 청소를 합니다.

0  0  0  0  0  0  0  0  0
56 57 46 45 44 43 42 41  0
55 48 47  0  0  0  0 40  0
50 49  0  0 36 37 38 39  0
51  0  0 35 34 31 30  0  0
52 53 12 11 33 32 29 28  0
54 14 13 10  9  0  0 27  0
16 15  2  1  8  0  0 26  0
17 18  3  4  7  0  0 25  0
21 19 20  5  6 22 23 24  0
0  0  0  0  0  0  0  0  0

cheonilchu 5년 전 0

항상 답변 주시는 @djm03178님 감사합니다 ㅎㅎ

시작점이랑 조건이 조금 잘못되었던 것 같습니다.

힌트를 주신덕분에 시작점이랑 조건을 찾을 수 있었습니다.

감사합니다!!

kimjh9434 4년 전 0

아... " 현재 방향을 기준으로 왼쪽방향부터 차례대로 탐색을 진행한다."의 의미가 이거였군요.

일단 꺽고 시작하는거였군요.

저는 현재 방향에 청소할수 있다면[벽x , 아직청소x] 그대로 가고, 아니면 그때 왼쪽[반시계방향]으로 꺽는다고 생각해서...

그랬더니 예시 2번의 답이 계속 52가 나와서 뭔가했네요. 먼저 꺽도록 수정하니까 문제 풀렸습니다!

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

손으로 그렸을때는 맞는것 같은데...TC에서는 틀리게 나옵니다

cheonilchu 5년 전 0

djm03178 5년 전 0

cheonilchu 5년 전 0

kimjh9434 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말