글 읽기 - 로직 똑같은 것 같은데 왜 답이 다르게 나오는지 잘 모르겠습니다!!

park780172 5년 전 0

......
......
......
......
......
......
......
......
......
......
RRYY..
RRYY..

위에 테스트 케이스를 실행하면 답이 1 입니다.

하지만 제가 첨부한 코드를 보면 108~116번 째 코드를 실행하면, 2가 나오고
118 ~ 127(주석)번 째 코드를 실행하면 1이 나옵니다.

108~116 코드과 118 ~ 127 코드

로직이 분명 똑같은데, 왜 답이 다르게 나오는지 모르겠습니다.

while로 풀려고 하는데 잘 안 됩니다..

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

// BOJ 11559 Puyo Puyo

#include <iostream>
#include <queue>
#include <cstdio>
#include <vector>
#include <cstring>
#include <string>
#include <math.h>
#include <algorithm>

using namespace std;

char map[12][6];

bool visit[12][6] = { false, };

int len = 0;

int cnt = 0;

int dy[4] = { -1, 0, 1, 0 };
int dx[4] = { 0, -1, 0, 1 };

void DFS(int row, int column, char character)
{
	++len;

	visit[row][column] = true;

	for (int i = 0; i < 4; i++)
	{
		int y = row + dy[i];
		int x = column + dx[i];

		if (0 <= y && y < 12 && 0 <= x && x < 6 && !visit[y][x] && map[y][x] == character)
		{
			DFS(y, x, character);
		}
	}
}

void mapEdit(int row, int column, char character) // DFS
{
	map[row][column] = '.';

	for (int i = 0; i < 4; i++)
	{
		int y = row + dy[i];
		int x = column + dx[i];

		if (0 <= y && y < 12 && 0 <= x && x < 6 && map[y][x] == character)
		{
			mapEdit(y, x, character);
		}
	}
}

int main(void)
{
	int ans = 0;

	for (int i = 0; i < 12; i++)
	{
		for (int j = 0; j < 6; j++)
		{
			cin >> map[i][j];
		}
	}

	while (true)
	{
		memset(visit, false, sizeof(visit));

		cnt = 0;

		for (int i = 0; i < 12; i++)
		{
			for (int j = 0; j < 6; j++)
			{
				if (!visit[i][j] && map[i][j] != '.') // Before DFS, Remember condition
				{
					len = 0;

					DFS(i, j, map[i][j]);

					if (len >= 4)
					{
						++cnt;

						mapEdit(i, j, map[i][j]); // from character to '.'
					}
				}
			}
		}

		// map change
		for (int column = 0; column < 6; column++)
		{
			for (int row = 11; row >= 0; row--)
			{
				if (map[row][column] == '.')
				{
					int replace_row = row - 1;

					while (replace_row >= 0 && map[replace_row][column] == '.')
					{
						--replace_row;
					}

					if (map[replace_row][column] != '.')
					{
						swap(map[replace_row][column], map[row][column]);
					}

					//for (int replace_row = row - 1; replace_row >= 0; replace_row--)
					//{
					//	if (map[replace_row][column] != '.')
					//	{
					//		char temp = map[replace_row][column];
					//		map[replace_row][column] = map[row][column];
					//		map[row][column] = temp;
					//		break; // 어차피 위의 2중 for문으로 인해 다음 map칸이 적용 되기 때문에 한 번 바꿔주면 바로 break
					//	}
					//}
				}
			}

		}

		if (cnt == 0) break;
		else ++ans;

	}

	printf("%d\n", ans);

	return 0;
}

djm03178 5년 전 1

113번째 줄에 도달할 때는 replace_row가 -1일 가능성도 있습니다. 이 때 map[-1][column]은 무엇이 될까요?

반면에 120번째 줄은 그런 걱정이 없습니다.

park780172 5년 전 0

아이고 왜 이런 간단한 것을 생각하지 못 했는지ㅠㅠ..
어제 계속 고민했었는데..
댓글 감사합니다!

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

문제

문제

출처

ICPC

로직 똑같은 것 같은데 왜 답이 다르게 나오는지 잘 모르겠습니다!!

park780172 5년 전 0

djm03178 5년 전 1

park780172 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말