Can I patent the same idea with my own methodology?
You can obtain a patent incorporating the same idea as long as your own methodology is a non-obvious improvement over the prior art (including but not limited to that specific competitor's patent). The claims will have to include some of the methodology details to render them non-obvious.
Is it illegal to use an idea which is already patented?
Ideas themselves cannot be patented. It is an act of infringement to practice a patented invention, as defined by its claims and the relevant statutes governing patent infringement. Patent infringement is not a criminal offense. At most, you would be liable for monetary damages and you may have to cease operations if a patent holder obtains an injunction against you.
As always, you should consult a patent attorney who can look at all the details of your situation.